Given a numeric string S, the task is to find the number of ways to partition a string into substrings consisting of digits in increasing order.
Examples:
Input: S = “1345”
Output: 5
Explanation: Possible partitions are as follows:
- [1345]
- [13, 45], [1, 345]
- [1, 3, 45]
- [1, 3, 4, 5]
Input: S = “12”
Output: 2
Approach: This problem can be solved by observing that between each digit either it will be a part of the previous number or it will be a new number so to solve the problem recursion can be used. Follow the steps below to solve the problem:
- Initialize an integer variable, say count as 0, to store the number of ways to partition a string into increasing subsets.
- Declare a function print() with index(storing current position), string S(given string in the question), and string ans( as parameters.
- Now, following two cases are required to be considered:
- If S[index] is inserted in the previous number, then append S[index] at the end of ans and recall the function print() with parameters index + 1, S, and ans.
- If S[index] is not a part of the previous number, then append ” “(space) at the end of ans and then insert S[index] and recall the function print() with parameters index + 1, S, ans.
- If index = S.length(), then check if the digits in the sequences formed are in increasing order or not. If the sequences formed are increasing, increase count by 1.
- Print count as the answer after performing the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Stores the number of ways// to partition a stringint count1 = 0;vector<string> split(string str){ vector<string> ans; string word = ""; for(auto x : str) { if (x == ' ') { ans.push_back(word); word = ""; } else { word = word + x; } } ans.push_back(word); return ans;}// Function to check if a sequence// is strictly increasing or notbool check(string m){ // If there is only one number if (m.length() == 1) { return true; } // Split the string m when there is space vector<string> temp = split(m); int number[temp.size()]; // Insert all the splits into the array for(int i = 0; i < temp.size(); ++i) { number[i] = stoi(temp[i]); } int first = number[0]; for(int i = 1; i < temp.size(); ++i) { if (number[i] > first) { first = number[i]; } else { // If number is not increasing return false; } } // If the sequence is increasing return true;}// Recursive function to partition// a string in every possible substringsvoid print1(string m, int index, string ans){ // If index = m.length, check if ans // forms an increasing sequence or not if (index == m.length()) { if (check(ans)) { // Increment count by 1, // if sequence is increasing count1++; } return; } // If S[index] is appended to previous number print1(m, index + 1, ans + m[index]); if (index != 0) // If S[index] is starting a new number print1(m, index + 1, ans + " " + m[index]);}// Driver Codeint main(){ // Given Input string k = "1345"; // Function Call print1(k, 0, ""); // Print the answer. cout << count1;}// This code is contributed by ipg2016107 |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Stores the number of ways // to partition a string static int count = 0; // Function to check if a sequence // is strictly increasing or not static boolean check(String m) { // If there is only one number if (m.length() == 1) { return true; } // Split the string m when there is space String temp[] = m.split(" "); int number[] = new int[temp.length]; // Insert all the splits into the array for (int i = 0; i < temp.length; ++i) { number[i] = Integer.parseInt(temp[i]); } int first = number[0]; for (int i = 1; i < number.length; ++i) { if (number[i] > first) { first = number[i]; } else { // If number is not increasing return false; } } // If the sequence is increasing return true; } // Recursive function to partition // a string in every possible substrings static void print(String m, int index, String ans) { // If index = m.length, check if ans // forms an increasing sequence or not if (index == m.length()) { if (check(ans)) { // Increment count by 1, // if sequence is increasing ++count; } return; } // If S[index] is appended to previous number print(m, index + 1, ans + m.charAt(index)); if (index != 0) // If S[index] is starting a new number print(m, index + 1, ans + " " + m.charAt(index)); } // DriverCode public static void main(String[] args) { // Given Input String k = Integer.toString(1345); // Function Call print(k, 0, ""); // Print the answer. System.out.println(count); }} |
Python3
# Python3 program for the above approachcount = 0 # Function to check if a sequence# is strictly increasing or notdef check(m): # If there is only one number if (len(m) == 1): return True # Split the string m when there is space temp = m.split(" ") number = [0]*(len(temp)) # Insert all the splits into the array for i in range(len(temp)): number[i] = int(temp[i]) first = number[0] for i in range(1, len(number)): if (number[i] > first): first = number[i] else: # If number is not increasing return False # If the sequence is increasing return True# Recursive function to partition# a string in every possible substringsdef Print(m, index, ans): global count # If index = m.length, check if ans # forms an increasing sequence or not if (index == len(m)): if (check(ans)): # Increment count by 1, # if sequence is increasing count+=1 return # If S[index] is appended to previous number Print(m, index + 1, ans + m[index]) if (index != 0): # If S[index] is starting a new number Print(m, index + 1, ans + " " + m[index])# Given Inputk = "1345" # Function CallPrint(k, 0, "") # Print the answer.print(count)# This code is contributed by suresh07. |
C#
using System;public class GFG { static int count = 0; // Function to check if a sequence // is strictly increasing or not static bool check(String m) { // If there is only one number if (m.Length == 1) { return true; } // Split the string m when there is space String[] temp = m.Split(" "); int[] number = new int[temp.Length]; // Insert all the splits into the array for (int i = 0; i < temp.Length; ++i) { number[i] = int.Parse(temp[i]); } int first = number[0]; for (int i = 1; i < number.Length; ++i) { if (number[i] > first) { first = number[i]; } else { // If number is not increasing return false; } } // If the sequence is increasing return true; } // Recursive function to partition // a string in every possible substrings static void print(String m, int index, String ans) { // If index = m.length, check if ans // forms an increasing sequence or not if (index == m.Length) { if (check(ans)) { // Increment count by 1, // if sequence is increasing ++count; } return; } // If S[index] is appended to previous number print(m, index + 1, ans + m[index]); if (index != 0) // If S[index] is starting a new number print(m, index + 1, ans + " " + m[index]); } static public void Main() { String k = "1345"; // Function Call print(k, 0, ""); // Print the answer. Console.WriteLine(count); }}// This code is contributed by maddler. |
Javascript
<script>// JavaScript program for the above approach// Stores the number of ways// to partition a stringlet count = 0;// Function to check if a sequence// is strictly increasing or notfunction check(m){ // If there is only one number if (m.length == 1) { return true; } // Split the string m when there is space let temp = m.split(" "); let number = new Array(temp.length); // Insert all the splits into the array for(let i = 0; i < temp.length; ++i) { number[i] = parseInt(temp[i]); } let first = number[0]; for(let i = 1; i < number.length; ++i) { if (number[i] > first) { first = number[i]; } else { // If number is not increasing return false; } } // If the sequence is increasing return true;}// Recursive function to partition// a string in every possible substringsfunction print(m, index, ans){ // If index = m.length, check if ans // forms an increasing sequence or not if (index == m.length) { if (check(ans)) { // Increment count by 1, // if sequence is increasing ++count; } return; } // If S[index] is appended to previous number print(m, index + 1, ans + m[index]); if (index != 0) // If S[index] is starting a new number print(m, index + 1, ans + " " + m[index]);}// Driver Code// Given Inputlet k = "1345";// Function Callprint(k, 0, "");// Print the answer.document.write(count);// This code is contributed by code_hunt</script> |
Output:
5
Time Complexity: O(N*2N) where N is the length of string S
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
