Concatenate the strings in an order which maximises the occurrence of subsequence " ab " | Java implementation of the approach ; Custom sort function to sort the given string in the order which maximises the final score ; To store the count of occurrences of ' a ' and ' b ' in s1 ; Count the number of occurrences of ' a ' and ' b ' in s1 ; To store the count of occurrences of ' a ' and ' b ' in s2 ; Count the number of occurrences of ' a ' and ' b ' in s2 ; Since the number of subsequences ' ab ' is more when s1 is placed before s2 we return 1 so that s1 occurs before s2 in the combined string ; Function that return the concatenated string as S [ 0 ] + S [ 1 ] + ... + S [ N - 1 ] ; To store the concatenated string ; Concatenate every string in the order of appearance ; Return the concatenated string ; Function to return the maximum required score ; Sort the strings in the order which maximizes the score that we can get ; Get the concatenated string combined string ; Calculate the score of the combined string i . e . the count of occurrences of " ab " as subsequences ; Number of ' a ' has increased by one ; There are count_a number of ' a ' that can form subsequence ' ab ' with this ' b ' ; Driver code
import java . util . * ; class Gfg { public static boolean customSort ( String s1 , String s2 ) { int count_a1 = 0 , count_b1 = 0 ; for ( int i = 0 ; i < s1 . length ( ) ; i ++ ) { if ( s1 . charAt ( i ) == ' a ' ) { count_a1 ++ ; } else { count_b1 ++ ; } } int count_a2 = 0 , count_b2 = 0 ; for ( int i = 0 ; i < s2 . length ( ) ; i ++ ) { if ( s2 . charAt ( i ) == ' a ' ) { count_a2 ++ ; } else { count_b2 ++ ; } } if ( count_a1 * count_b2 > count_b1 * count_a2 ) { return true ; } else { return false ; } } public static String concatenateStrings ( String S [ ] , int N ) { String str = " " ; for ( int i = 0 ; i < N ; i ++ ) { str += S [ i ] ; } return str ; } public static int getMaxScore ( String S [ ] , int N ) { Arrays . sort ( S ) ; String combined_string = concatenateStrings ( S , N ) ; int final_score = 0 , count_a = 0 ; for ( int i = 0 ; i < combined_string . length ( ) ; i ++ ) { if ( combined_string . charAt ( i ) == ' a ' ) { count_a ++ ; } else { final_score += count_a ; } } return final_score ; } public static void main ( String [ ] args ) { String S [ ] = { " aa " , " bb " , " aab " , " bab " } ; int N = S . length ; System . out . println ( getMaxScore ( S , N ) - 10 ) ; } }