Data Modelling & AI Data Structure & Algorithm

Concatenate the strings in an order which maximises the occurrence of subsequence “ab”

30 July 2024

0

Given N strings containing of characters ‘a’ and ‘b’. These string can be concatenated in any order to make a single final string S. The score of the final string S is defined as the number of occurrences of the subsequence “ab” in it. Now, the task is to concatenate the string in such a way that the score of the final string is maximized. Print the score of the final string.
Examples:

Input: arr[] = {“bab”, “aa”, “ba”, “b”}
Output: 13
If we combine the strings in the order arr[1] + arr[2] + arr[0] + arr[3]
then the final string will be “aabababb” which has a maximum score of 13.
Input: arr[] = {“aaba”, “ab”, “ba”}
Output: 10

Approach: Let us take any two strings S $_{i}$ and S $_{j}$ where 1 <= i, j <= N
Let number of occurrences of ‘a’ and ‘b’ in S $_{i}$ be count $_{i, a}$ and count $_{i, b}$ respectively.
Similarly, let number of occurrences of ‘a’ and ‘b’ in S $_{j}$ be count $_{j, a}$ and count $_{j, b}$ respectively.
Also, let count of subsequences ‘ab’ within S $_{i}$ and S $_{j}$ be score $_{i}$ and score $_{j}$ respectively.
We will calculate number of subsequences ‘ab’ in S $_{i}$ + S $_{j}$ assuming that S $_{i}$ occurs before S $_{j}$ in the combined string:

ans $_{1}$ = score $_{i}$ + score $_{j}$ + count $_{i, a}$ *count $_{j, b}$

as each ‘a’ in S $_{i}$ will combine with each ‘b’ in S $_{j}$ to create subsequence ‘ab’.
If we assume S $_{j}$ to occur before S $_{i}$ , similarly:

ans $_{2}$ = score $_{j}$ + score $_{i}$ + count $_{j, a}$ *count $_{i, b}$

So, if ans $_{1}$ > ans $_{2}$ then we have to place S $_{i}$ before S $_{j}$ , else we will place S $_{j}$ before S $_{i}$ .
Note that the value of score $_{i}$ and score $_{j}$ does not matter while sorting as they contribute to ans $_{1}$ and ans $_{2}$ equally.
It is therefore sufficient to check if count $_{i, a}$ *count $_{j, b}$ > count $_{j, a}$ *count $_{i, b}$ .
We can do this using a custom sort function as implemented in the code below.
Finally, we need to count such subsequences ‘ab’ in the combined string. For every occurrence of ‘b’, it can be combined with any ‘a’ that occurred before it to make the subsequence ‘ab’.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Custom sort function to sort the given string in
// the order which maximises the final score
bool customSort(string s1, string s2)
{
    // To store the count of occurrences
    // of 'a' and 'b' in s1
    int count_a1 = 0, count_b1 = 0;
 
    // Count the number of occurrences
    // of 'a' and 'b' in s1
    for (int i = 0; i < s1.size(); i++) {
        if (s1[i] == 'a')
            count_a1++;
        else
            count_b1++;
    }
 
    // To store the count of occurrences
    // of 'a' and 'b' in s2
    int count_a2 = 0, count_b2 = 0;
 
    // Count the number of occurrences
    // of 'a' and 'b' in s2
    for (int i = 0; i < s2.size(); i++) {
        if (s2[i] == 'a')
            count_a2++;
        else
            count_b2++;
    }
 
    // 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
    if (count_a1 * count_b2 > count_b1 * count_a2) {
        return 1;
    }
    else {
        return 0;
    }
}
 
// Function that return the concatenated
// string as S[0] + S[1] + ... + S[N - 1]
string concatenateStrings(string S[], int N)
{
 
    // To store the concatenated string
    string str = "";
 
    // Concatenate every string in
    // the order of appearance
    for (int i = 0; i < N; i++)
        str += S[i];
 
    // Return the concatenated string
    return str;
}
 
// Function to return the maximum required score
int getMaxScore(string S[], int N)
{
 
    // Sort the strings in the order which maximizes
    // the score that we can get
    sort(S, S + N, customSort);
 
    // Get the concatenated string combined string
    string combined_string = concatenateStrings(S, N);
 
    // Calculate the score of the combined string i.e.
    // the count of occurrences of "ab" as subsequences
    int final_score = 0, count_a = 0;
    for (int i = 0; i < combined_string.size(); i++) {
        if (combined_string[i] == 'a') {
 
            // Number of 'a' has increased by one
            count_a++;
        }
        else {
 
            // There are count_a number of 'a'
            // that can form subsequence 'ab'
            // with this 'b'
            final_score += count_a;
        }
    }
 
    return final_score;
}
 
// Driver code
int main()
{
    string S[] = { "bab", "aa", "ba", "b" };
    int N = sizeof(S) / sizeof(string);
 
    cout << getMaxScore(S, N);
 
    return 0;
}

Java

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

Python 3

# Python 3 implementation of the approach
 
# Custom sort function to sort the given string in
# the order which maximises the final score
def customSort(s1, s2):
     
    # To store the count of occurrences
    # of 'a' and 'b' in s1
    count_a1 = 0
    count_b1 = 0
 
    # Count the number of occurrences
    # of 'a' and 'b' in s1
    for i in range(len(s1)):
        if (s1[i] == 'a'):
            count_a1 += 1
        else:
            count_b1 += 1
 
    # To store the count of occurrences
    # of 'a' and 'b' in s2
    count_a2 = 0
    count_b2 = 0
 
    # Count the number of occurrences
    # of 'a' and 'b' in s2
    for i in range(len(s2)):
        if(s2[i] == 'a'):
            count_a2 += 1
        else:
            count_b2 += 1
 
    # 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
    if (count_a1 * count_b2 > count_b1 * count_a2):
        return 1
    else:
        return 0
 
# Function that return the concatenated
# string as S[0] + S[1] + ... + S[N - 1]
def concatenateStrings(S, N):
     
    # To store the concatenated string
    str = ""
 
    # Concatenate every string in
    # the order of appearance
    for i in range(N):
        str += S[i]
 
    # Return the concatenated string
    return str
 
# Function to return the maximum required score
def getMaxScore(S, N):
     
    # Sort the strings in the order which maximizes
    # the score that we can get
    S.sort()
 
    # Get the concatenated string combined string
    combined_string = concatenateStrings(S, N)
 
    # Calculate the score of the combined string i.e.
    # the count of occurrences of "ab" as subsequences
    final_score = 0
    count_a = 0
    for i in range(len(combined_string)):
        if (combined_string[i] == 'a'):
             
            # Number of 'a' has increased by one
            count_a += 1
        else:
             
            # There are count_a number of 'a'
            # that can form subsequence 'ab'
            # with this 'b'
            final_score += count_a
 
    return final_score
 
# Driver code
if __name__ == '__main__':
    S = ["aa", "bb", "aab", "bab"]
    N = len(S)
    print(getMaxScore(S, N)-10)
         
# This code is contributed by Surendra_Gangwar

C#

// C# implementation of the approach
using System;
class GFG
{
   
  // Custom sort function to sort the given string in 
  // the order which maximises the final score 
  static bool customSort(string s1, string s2)
  {
    // To store the count of occurrences 
    // of 'a' and 'b' in s1 
    int count_a1 = 0, count_b1 = 0; 
 
    // Count the number of occurrences 
    // of 'a' and 'b' in s1
    for(int i = 0; i < s1.Length; i++)
    {
      if(s1[i] == 'a')
      {
        count_a1++;
      }
      else
      {
        count_b1++;
      }
 
    }
 
    // To store the count of occurrences 
    // of 'a' and 'b' in s2 
    int count_a2 = 0, count_b2 = 0;
 
    // Count the number of occurrences 
    // of 'a' and 'b' in s2
    for(int i = 0; i < s1.Length; i++)
    {
      if(s2[i] == 'a')
      {
        count_a2++;
      }
      else
      {
        count_b2++;
      }
 
    }
 
    // 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
    if(count_a1 * count_b2 > count_b1 * count_a2)
    {
      return true;
    }
    else
    {
      return false;
    }
  }
 
  // Function that return the concatenated 
  // string as S[0] + S[1] + ... + S[N - 1]
  static string concatenateStrings(string[] S, int N)
  {
 
    // To store the concatenated string 
    string str = "";
 
    // Concatenate every string in 
    // the order of appearance
    for(int i = 0; i < N; i++)
    {
      str += S[i]; 
    }
 
    // Return the concatenated string
    return str;
  }
 
  // Function to return the maximum required score 
  static int getMaxScore(string[] S, int N)
  {
 
    // Sort the strings in the order which maximizes 
    // the score that we can get
    Array.Sort(S);
 
    // Get the concatenated string combined string 
    string combined_string = concatenateStrings(S, N);
 
    // Calculate the score of the combined string i.e. 
    // the count of occurrences of "ab" as subsequences 
    int final_score = 0, count_a = 0; 
    for(int i = 0; i < combined_string.Length; i++)
    {
      if(combined_string[i] == 'a')
      {
 
        // Number of 'a' has increased by one 
        count_a++; 
      }
      else
      {
 
        // There are count_a number of 'a' 
        // that can form subsequence 'ab' 
        // with this 'b' 
        final_score += count_a; 
      }
    }
    return final_score; 
  }
 
  // Driver code 
  static public void Main ()
  {
    string[] S = {"aa", "bb", "aab", "bab"};
    int N = S.Length;
    Console.WriteLine(getMaxScore(S, N) - 10);
  }
}
 
// This code is contributed by rag2127

Javascript

<script>
 
// Javascript implementation of the approach
 
// Custom sort function to sort the given string in
    // the order which maximises the final score
function customSort(s1,s2)
{
    // To store the count of occurrences
        // of 'a' and 'b' in s1
        let count_a1 = 0, count_b1 = 0;
          
        // Count the number of occurrences
        // of 'a' and 'b' in s1
        for(let i = 0; i < s1.length; i++)
        {
            if(s1[i] == 'a')
            {
                count_a1++;
            }
            else
            {
                count_b1++;
            }
        }
          
        // To store the count of occurrences
        // of 'a' and 'b' in s2
        let count_a2 = 0, count_b2 = 0;
          
        // Count the number of occurrences
        // of 'a' and 'b' in s2
        for(let i = 0; i < s2.length; i++)
        {
            if(s2[i] == 'a')
            {
                count_a2++;
            }
            else
            {
                count_b2++;
            }
        }
          
        // 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
        if(count_a1 * count_b2 > count_b1 * count_a2)
        {
            return true;
        }
        else
        {
            return false;
        }
}
 
// Function that return the concatenated
    // string as S[0] + S[1] + ... + S[N - 1]
function concatenateStrings(S,N)
{
    // To store the concatenated string
        let str="";
          
        // Concatenate every string in
        // the order of appearance
        for(let i = 0; i < N; i++)
        {
            str += S[i];
        }
          
        // Return the concatenated string
        return str;
}
 
// Function to return the maximum required score
function getMaxScore(S,N)
{
    // Sort the strings in the order which maximizes
        // the score that we can get
        S.sort();
          
        // Get the concatenated string combined string
        let combined_string = concatenateStrings(S, N);
          
        // Calculate the score of the combined string i.e.
        // the count of occurrences of "ab" as subsequences
        let final_score = 0, count_a = 0;
          
        for (let i = 0; i < combined_string.length; i++) {
        if (combined_string[i] == 'a') {
    
            // Number of 'a' has increased by one
            count_a++;
        }
        else {
    
            // There are count_a number of 'a'
            // that can form subsequence 'ab'
            // with this 'b'
            final_score += count_a;
        }
    }
      
    return final_score;
}
 
// Driver code
let S=[ "aa", "bb", "aab", "bab"];
let N = S.length;
document.write(getMaxScore(S, N) - 10);
 
 
// This code is contributed by ab2127
</script>

Output:

Time Complexity: O(N * log N)

Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Concatenate the strings in an order which maximises the occurrence of subsequence “ab”

C++

Java

Python 3

C#

Javascript

Run Local AWS Cloud Stack using LocalStack on Linux

Learn Terraform Automation in 3 days using Video Courses

How To Expose Ansible AWX Service using Nginx Ingress

LEAVE A REPLY Cancel reply

Most Popular

How to Secure Your Network-Attached Storage (NAS) in 2024 by Tyler Cross

8 Best Private Search Engines in 2024: Tested by Experts by Tyler Cross

The biggest comeback in tech history [Video]

Google wants to hear your thoughts on the Android 15 QPR2 Beta

Recent Comments

EDITOR PICKS

How to Secure Your Network-Attached Storage (NAS) in 2024 by Tyler Cross

8 Best Private Search Engines in 2024: Tested by Experts by Tyler Cross

The biggest comeback in tech history [Video]

POPULAR POSTS

How to Secure Your Network-Attached Storage (NAS) in 2024 by Tyler Cross

8 Best Private Search Engines in 2024: Tested by Experts by Tyler Cross

The biggest comeback in tech history [Video]

POPULAR CATEGORY

ABOUT US

FOLLOW US