Lengths of maximized partitions of a string such that each character of the string appears in one substring | C ++ program for the above approach ; Function to find the length of all partitions oof a string such that each characters occurs in a single substring ; Stores last index of string s ; Find the last position of each letter in the string ; Update the last index ; Iterate the given string ; Get the last index of s [ i ] ; Extend the current partition characters last pos ; Increase len of partition ; if the current pos of character equals the min pos then the end of partition ; Store the length ; Print all the partition lengths ; Driver Code ; Given string str ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void partitionString ( string s ) { int n = s . size ( ) ; vector < int > ans ; if ( n == 0 ) { cout << " - 1" ; return ; } vector < int > last_pos ( 26 , -1 ) ; for ( int i = n - 1 ; i >= 0 ; -- i ) { if ( last_pos [ s [ i ] - ' a ' ] == -1 ) { last_pos [ s [ i ] - ' a ' ] = i ; } } int minp = -1 , plen = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int lp = last_pos [ s [ i ] - ' a ' ] ; minp = max ( minp , lp ) ; ++ plen ; if ( i == minp ) { ans . push_back ( plen ) ; minp = -1 ; plen = 0 ; } } for ( int i = 0 ; i < ( int ) ans . size ( ) ; i ++ ) { cout << ans [ i ] << " ▁ " ; } } int main ( ) { string str = " acbbcc " ; partitionString ( str ) ; return 0 ; }