Count the number of ways to split a string into K substrings starting with an even number and having a minimum length of M

In this problem, we will calculate the way to divide the given string into K substrings such that it satisfies the conditions given in the problem statement.

We will use recursion to solve this problem. Additionally, we will use tabular dynamic programming methods to efficiently solve this problem.

Problem Statement − We have a string of specific length called bin_Str. The string contains only numeric characters from '0' to '9'. We need to calculate the number of ways to split the string into K substrings such that it satisfies the following conditions.

• The substring should contain at least 2 characters.

• The first character of each substring should be even and the last character should be odd.

ExampleExample

enter

M = 2, K = 2; bin_str = "255687"

Output

1

Explanation − Based on the conditions of the problem statement, we can split 255 | 687 into parts of the given string.

enter

M = 2, K = 2; bin_str = "26862";

Output

0

Explanation − Since the string contains only even numbers, we cannot split it into two substrings such that each substring ends with an odd number.

enter

M = 2, K = 3; bin_str = "856549867";

Output

3

Explanation − Possible partitioning methods are 85|65|49867, 8565|49|867 and 85|6549|867.

method one

We will use a recursive function to solve this problem. If we find a valid substring at the current index, we make a recursive call counting the number of ways to split the remaining substring into K - 1 substrings.

algorithm

Step 1 − Get the first and last characters of the given string.

Step 2 − If the first character is not even and the last character is not odd, return 0.

Step 3 − If the starting index is equal to the string length, return 0 because we have reached the end of the given string.

Step 4− If K == 1, take the difference between the string length and the starting index. If it is equal to or greater than M, then 1 is returned. Otherwise, returns 0. Here, if K is 1, we need to get the remaining substring.

Step 5 - Initialize 'ops' to '0' to store the count of splitting methods, and initialize 'len' to '0' to store the length of the current substring.

Step 6 − Traverse the string starting from the "start" index until the end of the string.

Step 7− Increase ‘len’ by 1. At the same time, get the current character and the next character.

Step 8− If 'len' is greater than M, and the current number is odd and the next number is even, we can end the partition at the current index. So, make a recursive call to the countWays() function by passing the next index and K - 1 as function arguments.

Step 9− Finally, return the value of ‘ops’.

Example

#include <bits/stdc++.h>
using namespace std;

int countWays(int start, int str_len, int K, int M, string bin_str) {
    // Geeting first and last character of the substring
    int f_char = bin_str[0] - '0';
    int l_char = bin_str[str_len - 1] - '0';
    if (f_char % 2 != 0 || l_char % 2 != 1) {
        return 0;
    }
    // When we reach at the end
    if (start == str_len)
        return 0;
    // Base case
    if (K == 1) {
        int chars = str_len - start;
        // Validate minimum length of substring
        if (chars >= M)
            return 1;
        return 0;
    }    
    int ops = 0;
    int len = 0;
    // Traverse all partions
    for (int p = start; p < str_len - 1; p++) {
        len++;
        int first = bin_str[p] - '0';
        int second = bin_str[p + 1] - '0';
        // If we can end the partition at p and start a new partition at p+1
        if (len >= M && first % 2 == 1) {
            if (second % 2 == 0) {
                ops += countWays(p + 1, str_len, K - 1, M, bin_str);
            }
        }
    }
    return ops;
}
int main() {
    int M = 2, K = 2;
    string bin_str = "255687";
    int str_len = bin_str.length();
    cout << "The number of ways to split the string is " << countWays(0, str_len, K, M, bin_str) << endl;
    return 0;
}

Output

The number of ways to split the string is 1

The number of ways to split a string is 1

Space Complexity - O(1) since we don't use extra space.

Method Two

In this method, we will use tabular dynamic programming techniques to calculate the number of ways to split the string into K parts. We will use a matrix to store the output of the previous state.

algorithm

Step 1 - Define a global matrix matrix[] array of size 1001 x 1001. The rows of the matrix map to a string character, and the columns of the matrix map to K.

Step 2 − Get the first and last characters of the string. If the first character is even and the last character is odd, the countWays() function is executed. Otherwise, print 0 in the output.

Step 3 − In the countWays function, initialize the matrix[] array.

Step 4 − The number of rows of the traversed matrix is ​​equal to the length of the string, and the number of columns is equal to K. If the number of rows is equal to the string length, update the entire row to 0.

Step 5 − Otherwise, if q is 1 and the string length minus the current index is greater than M, initialize the array matrix[p][q] with 1. Otherwise, initialize matrix[p][q] with 0.

Step 6 − In other cases, initialize matrix [p][q] to -1.

Step 7− Use two nested loops to fill the matrix. Use an outer loop to traverse from 2 to K, and use a nested loop to traverse from 0 to the length of the string.

Step 8 - Initialize 'ops' and 'len' to 0. Additionally, iterate over the string starting at the p-th index and increment 'len' by 1 on each iteration.

Step 9 − Take out the current character and next character of the string.

Step 10− If the length is greater than M, the current character is odd, and the next character is even, add matrix[k 1][q − 1] to 'ops'.

Step 11− Use ‘ops’ to update matrix [p][q].

Step 12− Finally return matrix[0][k].

Example

示例

#include <bits/stdc++.h>
using namespace std;

int matrix[1001][1001];
int countWays(int str_len, int K, int M, string bin_str) {
    // Base case
    for (int p = 0; p <= str_len; p++) {
        for (int q = 0; q <= K; q++) {
            // When index points to end index of string
            if (p == str_len)
                matrix[p][q] = 0;
            else if (q == 1) {
                // When only 1 split needs to be done
                int chars = str_len - p;
                // Validating substring's minimum len
                if (chars >= M)
                    matrix[p][q] = 1;
                else
                    matrix[p][q] = 0;
            } else {
                // For other cases
                matrix[p][q] = -1;
            }
        }
    }
    // Dynamic programming approach
    for (int q = 2; q <= K; q++) {
        for (int p = 0; p < str_len; p++) {
            int ops = 0;
            int len = 0; // length of current substring
            for (int k = p; k < str_len - 1; k++) {
                len++;
                int first = bin_str[k] - '0';
                int second = bin_str[k + 1] - '0';
                // Validate condition for split
                if (len >= M && first % 2 == 1 && second % 2 == 0) {
                    // Substring starting from k + 1 index needs to be splited in q-1 parts
                    ops += matrix[k + 1][q - 1];
                }
            }
            matrix[p][q] = ops;
        }
    }
    return matrix[0][K];
}
int main() {
    int M = 2, K = 2;
    string bin_str = "255687";
    int str_len = bin_str.length();
    int f_char = bin_str[0] - '0';
    int l_char = bin_str[str_len - 1] - '0';
    cout << "The number of ways to split the string is ";
    if (f_char % 2 != 0 || l_char % 2 != 1) {
        cout << 0 << endl;
    } else {
        cout << countWays(str_len, K, M, bin_str) << endl;
    }
    return 0;
}

输出

The number of ways to split the string is 1

时间复杂度 - O(N*N*K)，其中 O(N*N) 用于找到所有子字符串，O(K) 用于 K 个分区。

空间复杂度 - 使用matrix[]数组为O(N*K)。

The above is the detailed content of Count the number of ways to split a string into K substrings starting with an even number and having a minimum length of M. For more information, please follow other related articles on the PHP Chinese website!