Maximize count of occurrences of S2 in S1 as a subsequence by concatenating N1 and N2 times respectively | Java program for the above approach ; Function to count maximum number of occurrences of s2 as subsequence in s1 by concatenating s1 , n1 times and s2 , n2 times ; Stores number of times s1 is traversed ; Stores number of times s2 is traversed ; Mapping index of s2 to number of times s1 and s2 are traversed ; Stores index of s1 circularly ; Stores index of s2 circularly ; Traverse the string s1 , n1 times ; If current character of both the string are equal ; Update j ; Update i ; If j is length of s2 ; Update j for circular traversal ; Update s2_reps ; If i is length of s1 ; Update i for circular traversal ; Update s1_reps ; If already mapped j to ( s1_reps , s2_reps ) ; Mapping j to ( s1_reps , s2_reps ) ; If s1 already traversed n1 times ; Otherwis , traverse string s1 by multiple of s1_reps and update both s1_reps and s2_reps ; Update s2_reps ; Update s1_reps ; If s1 is traversed less than n1 times ; If current character in both the string are equal ; Update j ; Update i ; If i is length of s1 ; Update i for circular traversal ; Update s1_reps ; If j is length of ss ; Update j for circular traversal ; Update s2_reps ; Driver Code
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static int getMaxRepetitions ( String s1 , int n1 , String s2 , int n2 ) { int temp1 [ ] = new int [ 26 ] , temp2 [ ] = new int [ 26 ] ; for ( char i : s1 . toCharArray ( ) ) temp1 [ i - ' a ' ] ++ ; for ( char i : s2 . toCharArray ( ) ) temp2 [ i - ' a ' ] ++ ; for ( int i = 0 ; i < 26 ; i ++ ) { if ( temp2 [ i ] > temp1 [ i ] ) return 0 ; } int s1_reps = 0 ; int s2_reps = 0 ; HashMap < Integer , int [ ] > s2_index_to_reps = new HashMap < > ( ) ; s2_index_to_reps . put ( 0 , new int [ ] { 0 , 0 } ) ; int i = 0 ; int j = 0 ; while ( s1_reps < n1 ) { if ( s1 . charAt ( i ) == s2 . charAt ( j ) ) j += 1 ; i += 1 ; if ( j == s2 . length ( ) ) { j = 0 ; s2_reps += 1 ; } if ( i == s1 . length ( ) ) { i = 0 ; s1_reps += 1 ; if ( ! s2_index_to_reps . containsKey ( j ) ) break ; s2_index_to_reps . put ( j , new int [ ] { s1_reps , s2_reps } ) ; } } if ( s1_reps == n1 ) return s2_reps / n2 ; int initial_s1_reps = s2_index_to_reps . get ( j ) [ 0 ] , initial_s2_reps = s2_index_to_reps . get ( j ) [ 1 ] ; int loop_s1_reps = s1_reps - initial_s1_reps ; int loop_s2_reps = s2_reps - initial_s2_reps ; int loops = ( n1 - initial_s1_reps ) ; s2_reps = initial_s2_reps + loops * loop_s2_reps ; s1_reps = initial_s1_reps + loops * loop_s1_reps ; while ( s1_reps < n1 ) { if ( s1 . charAt ( i ) == s2 . charAt ( j ) ) j += 1 ; i += 1 ; if ( i == s1 . length ( ) ) { i = 0 ; s1_reps += 1 ; } if ( j == s2 . length ( ) ) { j = 0 ; s2_reps += 1 ; } } return s2_reps / n2 ; } public static void main ( String [ ] args ) { String s1 = " acb " ; int n1 = 4 ; String s2 = " ab " ; int n2 = 2 ; System . out . println ( getMaxRepetitions ( s1 , n1 , s2 , n2 ) ) ; } }