Lengths of maximized partitions of a string such that each character of the string appears in one substring
Given string str of lowercase alphabets, split the given string into as many substrings as possible such that each character from the given string appears in a single substring. The task is to print the length of all such partitions.
Examples:
Input: str = “acbbcc”
Output: 1 5
Explanation:
Possible partitions where each character of the strings occurs in at most one partition are “a” and “cbbcc”.
Therefore, the length is {1, 5}Input: str = “abaccbdeffed”
Output: 6 6
Explanation:
Possible partitions where each character of the strings occurs in at most one partition are “abaccb” and “deffed”.
Therefore, the length is {6, 6}
Approach: This problem can be solved easily by using the Greedy Approach. Follow the steps given below to solve the problem.
- Store the last index of all characters in the string.
- Since the string contains only lowercase letters, simply use an array of fixed size 26 to store the last indices of each character.
- Iterate over the given string and follow the steps below:
- Add the current character to the partition if the last position of the character exceeds the current index and increase the length of the partition.
- If the last index of the current character is equal to the current index, then store its length and proceed to the next character and so on.
- After completing the above steps, print all the lengths stored.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the length of // all partitions of a string such // that each characters occurs in // a single substring void partitionString(string s) { int n = s.size(); // Stores last index of string s vector< int > ans; if (n == 0) { cout << "-1" ; return ; } // Find the last position of // each letter in the string vector< int > last_pos(26, -1); for ( int i = n - 1; i >= 0; --i) { // Update the last index if (last_pos[s[i] - 'a' ] == -1) { last_pos[s[i] - 'a' ] = i; } } int minp = -1, plen = 0; // Iterate the given string for ( int i = 0; i < n; ++i) { // Get the last index of s[i] int lp = last_pos[s[i] - 'a' ]; // Extend the current partition // characters last pos minp = max(minp, lp); // Increase len of partition ++plen; // if the current pos of // character equals the min pos // then the end of partition if (i == minp) { // Store the length ans.push_back(plen); minp = -1; plen = 0; } } // Print all the partition lengths for ( int i = 0; i < ( int )ans.size(); i++) { cout << ans[i] << " " ; } } // Driver Code int main() { // Given string str string str = "acbbcc" ; // Function Call partitionString(str); return 0; } |
Java
// Java program for // the above approach import java.util.*; class GFG{ // Function to find the length of // all partitions of a String such // that each characters occurs in // a single subString static void partitionString(String s) { int n = s.length(); // Stores last index of String s Vector<Integer> ans = new Vector<Integer>(); if (n == 0 ) { System.out.print( "-1" ); return ; } // Find the last position of // each letter in the String int []last_pos = new int [ 26 ]; Arrays.fill(last_pos, - 1 ); for ( int i = n - 1 ; i >= 0 ; --i) { // Update the last index if (last_pos[s.charAt(i) - 'a' ] == - 1 ) { last_pos[s.charAt(i) - 'a' ] = i; } } int minp = - 1 , plen = 0 ; // Iterate the given String for ( int i = 0 ; i < n; ++i) { // Get the last index of s[i] int lp = last_pos[s.charAt(i) - 'a' ]; // Extend the current partition // characters last pos minp = Math.max(minp, lp); // Increase len of partition ++plen; // if the current pos of // character equals the min pos // then the end of partition if (i == minp) { // Store the length ans.add(plen); minp = - 1 ; plen = 0 ; } } // Print all the partition lengths for ( int i = 0 ; i < ( int )ans.size(); i++) { System.out.print(ans.get(i) + " " ); } } // Driver Code public static void main(String[] args) { // Given String str String str = "acbbcc" ; // Function Call partitionString(str); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach # Function to find the length of # all partitions of a string such # that each characters occurs in # a single substring def partitionString(s): n = len (s) # Stores last index of string s ans = [] if (n = = 0 ): print ( "-1" ) return # Find the last position of # each letter in the string last_pos = [ - 1 ] * 26 for i in range (n - 1 , - 1 , - 1 ): # Update the last index if (last_pos[ ord (s[i]) - ord ( 'a' )] = = - 1 ): last_pos[ ord (s[i]) - ord ( 'a' )] = i minp = - 1 plen = 0 # Iterate the given string for i in range (n): # Get the last index of s[i] lp = last_pos[ ord (s[i]) - ord ( 'a' )] # Extend the current partition # characters last pos minp = max (minp, lp) # Increase len of partition plen + = 1 # if the current pos of # character equals the min pos # then the end of partition if (i = = minp): # Store the length ans.append(plen) minp = - 1 plen = 0 # Print all the partition lengths for i in range ( len (ans)): print (ans[i], end = " " ) # Driver Code # Given string str str = "acbbcc" # Function call partitionString( str ) # This code is contributed by code_hunt |
C#
// C# program for // the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the length of // all partitions of a String such // that each characters occurs in // a single subString static void partitionString(String s) { int n = s.Length; // Stores last index of String s List< int > ans = new List< int >(); if (n == 0) { Console.Write( "-1" ); return ; } // Find the last position of // each letter in the String int []last_pos = new int [26]; for ( int i = 0; i < 26; ++i) { last_pos[i] = -1; } for ( int i = n - 1; i >= 0; --i) { // Update the last index if (last_pos[s[i] - 'a' ] == -1) { last_pos[s[i] - 'a' ] = i; } } int minp = -1, plen = 0; // Iterate the given String for ( int i = 0; i < n; ++i) { // Get the last index of s[i] int lp = last_pos[s[i] - 'a' ]; // Extend the current partition // characters last pos minp = Math.Max(minp, lp); // Increase len of partition ++plen; // if the current pos of // character equals the min pos // then the end of partition if (i == minp) { // Store the length ans.Add(plen); minp = -1; plen = 0; } } // Print all the partition lengths for ( int i = 0; i < ( int )ans.Count; i++) { Console.Write(ans[i] + " " ); } } // Driver Code public static void Main(String[] args) { // Given String str String str = "acbbcc" ; // Function Call partitionString(str); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript program for the // above approach // Function to find the length of // all partitions of a String such // that each characters occurs in // a single subString function partitionString(s) { let n = s.length; // Stores last index of String s let ans = []; if (n == 0) { document.write( "-1" ); return ; } // Find the last position of // each letter in the String let last_pos = Array(26).fill(-1); for (let i = n - 1; i >= 0; --i) { // Update the last index if (last_pos[s[i].charCodeAt() - 'a' .charCodeAt()] == -1) { last_pos[s[i].charCodeAt() - 'a' .charCodeAt()] = i; } } let minp = -1, plen = 0; // Iterate the given String for (let i = 0; i < n; ++i) { // Get the last index of s[i] let lp = last_pos[s[i].charCodeAt() - 'a' .charCodeAt()]; // Extend the current partition // characters last pos minp = Math.max(minp, lp); // Increase len of partition ++plen; // if the current pos of // character equals the min pos // then the end of partition if (i == minp) { // Store the length ans.push(plen); minp = -1; plen = 0; } } // Print all the partition lengths for (let i = 0; i < ans.length; i++) { document.write(ans[i] + " " ); } } // Driver Code // Given String str let str = "acbbcc" ; // Function Call partitionString(str); // This code is contributed by avijitmondal1998. </script> |
1 5
Time Complexity: O(N)
Auxiliary Space: O(N)