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

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!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
C   XML Frameworks: Choosing the Right One for YouC XML Frameworks: Choosing the Right One for YouApr 30, 2025 am 12:01 AM

The choice of C XML framework should be based on project requirements. 1) TinyXML is suitable for resource-constrained environments, 2) pugixml is suitable for high-performance requirements, 3) Xerces-C supports complex XMLSchema verification, and performance, ease of use and licenses must be considered when choosing.

C# vs. C  : Choosing the Right Language for Your ProjectC# vs. C : Choosing the Right Language for Your ProjectApr 29, 2025 am 12:51 AM

C# is suitable for projects that require development efficiency and type safety, while C is suitable for projects that require high performance and hardware control. 1) C# provides garbage collection and LINQ, suitable for enterprise applications and Windows development. 2)C is known for its high performance and underlying control, and is widely used in gaming and system programming.

How to optimize codeHow to optimize codeApr 28, 2025 pm 10:27 PM

C code optimization can be achieved through the following strategies: 1. Manually manage memory for optimization use; 2. Write code that complies with compiler optimization rules; 3. Select appropriate algorithms and data structures; 4. Use inline functions to reduce call overhead; 5. Apply template metaprogramming to optimize at compile time; 6. Avoid unnecessary copying, use moving semantics and reference parameters; 7. Use const correctly to help compiler optimization; 8. Select appropriate data structures, such as std::vector.

How to understand the volatile keyword in C?How to understand the volatile keyword in C?Apr 28, 2025 pm 10:24 PM

The volatile keyword in C is used to inform the compiler that the value of the variable may be changed outside of code control and therefore cannot be optimized. 1) It is often used to read variables that may be modified by hardware or interrupt service programs, such as sensor state. 2) Volatile cannot guarantee multi-thread safety, and should use mutex locks or atomic operations. 3) Using volatile may cause performance slight to decrease, but ensure program correctness.

How to measure thread performance in C?How to measure thread performance in C?Apr 28, 2025 pm 10:21 PM

Measuring thread performance in C can use the timing tools, performance analysis tools, and custom timers in the standard library. 1. Use the library to measure execution time. 2. Use gprof for performance analysis. The steps include adding the -pg option during compilation, running the program to generate a gmon.out file, and generating a performance report. 3. Use Valgrind's Callgrind module to perform more detailed analysis. The steps include running the program to generate the callgrind.out file and viewing the results using kcachegrind. 4. Custom timers can flexibly measure the execution time of a specific code segment. These methods help to fully understand thread performance and optimize code.

How to use the chrono library in C?How to use the chrono library in C?Apr 28, 2025 pm 10:18 PM

Using the chrono library in C can allow you to control time and time intervals more accurately. Let's explore the charm of this library. C's chrono library is part of the standard library, which provides a modern way to deal with time and time intervals. For programmers who have suffered from time.h and ctime, chrono is undoubtedly a boon. It not only improves the readability and maintainability of the code, but also provides higher accuracy and flexibility. Let's start with the basics. The chrono library mainly includes the following key components: std::chrono::system_clock: represents the system clock, used to obtain the current time. std::chron

What is real-time operating system programming in C?What is real-time operating system programming in C?Apr 28, 2025 pm 10:15 PM

C performs well in real-time operating system (RTOS) programming, providing efficient execution efficiency and precise time management. 1) C Meet the needs of RTOS through direct operation of hardware resources and efficient memory management. 2) Using object-oriented features, C can design a flexible task scheduling system. 3) C supports efficient interrupt processing, but dynamic memory allocation and exception processing must be avoided to ensure real-time. 4) Template programming and inline functions help in performance optimization. 5) In practical applications, C can be used to implement an efficient logging system.

How to understand ABI compatibility in C?How to understand ABI compatibility in C?Apr 28, 2025 pm 10:12 PM

ABI compatibility in C refers to whether binary code generated by different compilers or versions can be compatible without recompilation. 1. Function calling conventions, 2. Name modification, 3. Virtual function table layout, 4. Structure and class layout are the main aspects involved.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor