Concatenate the strings in an order which maximises the occurrence of subsequence " ab " | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool customSort ( string s1 , string s2 ) { int count_a1 = 0 , count_b1 = 0 ; for ( int i = 0 ; i < s1 . size ( ) ; i ++ ) { if ( s1 [ i ] == ' a ' ) count_a1 ++ ; else count_b1 ++ ; } int count_a2 = 0 , count_b2 = 0 ; for ( int i = 0 ; i < s2 . size ( ) ; i ++ ) { if ( s2 [ i ] == ' a ' ) count_a2 ++ ; else count_b2 ++ ; } if ( count_a1 * count_b2 > count_b1 * count_a2 ) { return 1 ; } else { return 0 ; } } string concatenateStrings ( string S [ ] , int N ) { string str = " " ; for ( int i = 0 ; i < N ; i ++ ) str += S [ i ] ; return str ; } int getMaxScore ( string S [ ] , int N ) { sort ( S , S + N , customSort ) ; string combined_string = concatenateStrings ( S , N ) ; int final_score = 0 , count_a = 0 ; for ( int i = 0 ; i < combined_string . size ( ) ; i ++ ) { if ( combined_string [ i ] == ' a ' ) { count_a ++ ; } else { final_score += count_a ; } } return final_score ; } int main ( ) { string S [ ] = { " bab " , " aa " , " ba " , " b " } ; int N = sizeof ( S ) / sizeof ( string ) ; cout << getMaxScore ( S , N ) ; return 0 ; }