


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!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

Python is a popular programming language that provides many built-in functions to handle strings. One of the commonly used functions is the split() function, which can split a string into multiple substrings according to the specified delimiter. This article will introduce how to use the split() function in Python3.x. In Python, the split() function is a built-in function of the string class. Its basic syntax is as follows: string.split(separator,maxsplit)

In this article, we will explore the problem of how to find the length of the maximizing partition of a string with unique characters. We first understand the problem statement and then study naive and efficient methods to solve this problem, including their respective algorithms and time complexities. Finally, we will implement the solution in C++. Problem Statement Given a string, split the string into as many substrings as possible so that each character in the string appears in only one substring. Returns the length of these maximizing splits. Naive approach The naive approach is to iterate through the string, recording the last occurrence of each character. Then, iterate over the string again and create a partition when the last occurrence of the current character is found. Algorithm (naive) to initialize an array to store strings in

In this problem, we need to split the given string such that the third substring can be a substring of the first two substrings. Let's think of a solution. The third string can be a substring of the first two strings only if the first two strings contain all the characters of the third string. So, we need to find at least one character with frequency greater than 3 in the given string, and we can take the third substring of that single character. Problem Statement - We are given a string str containing N lowercase alphabetic characters. We need to check if we can split the string into three substrings a, b and c such that substring c is a substring of a and b. Depending on whether 3 substrings can be found, print "yes" or "no"

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. Substring should contain at least 2 characters. The first character of each substring should be even and the last character should be odd. ExampleExample inputM=2,K=2;bin_str="255687&q

There are many string functions in PHP, among which the string splitting function is very commonly used. The string split function can split a string according to the specified delimiter and return an array. Below we will introduce several commonly used string splitting functions. explode function The explode function can split a string according to the specified delimiter and return an array. The syntax is as follows: explode(string$separator,string$string

How to Split String into Array in PHP In PHP, we often need to process strings and split them into multiple parts. Splitting a string into an array is a common operation that helps us better handle the various parts of the string. In this article, we will learn how to split a string into an array using functions in PHP and provide some code examples. Use the explode function to split a string into an array. PHP provides a function called explode, which can split the string according to the specified delimiter.

The method to solve the error reported by the explode function in PHP requires specific code examples. In PHP, the explode function is a function used to split a string into an array according to the specified delimiter. However, sometimes an error occurs when using the explode function, mainly because the parameters passed in do not meet the requirements of the function. Below we will discuss possible problems and solutions in detail, and provide specific code examples. Error caused by wrong number of parameters when using explode function

In the PHP language, there are many basic functions that can help us process strings quickly and efficiently. Among them, the explode function is a very practical string splitting function. It can split a string into arrays according to the specified delimiter, and then perform more flexible string operations. In this article, we will introduce how to use the explode function to split strings in PHP. 1. The format of the explode function. The format of the explode function in the PHP language is as follows: explode(separa
