Split Strings into two Substrings whose distinct element counts are equal – GeeksforGeeks

Given a string S of length N, the task is to check if a string can be split into two non-intersecting strings such that the number of distinct characters are equal in both.

Examples:

Input: N = 6, S = “abccba”
Output: True
Explanation: Splitting two strings as “abc” and “cba” has 3 distinct characters each.

Input: N = 5, S = “aacaa”
Output: False
Explanation: Not possible to split it into two strings of the same distinct characters.

Approach: To solve the problem follow the below intuition:

The intuition behind solving the problem of checking if a string can be split into two parts such that both parts have the same number of distinct letters to keep track of the frequency of the characters in the string and compare it with the frequency of characters in the substrings as we iterate through the string.

Follow the below steps to solve the problem:

• Starts by storing the frequency of each character in the input string in an array called freq of size 26.
• Then, creates another array temp of size 26 to store the frequency of each character in a portion of the input string. 
• Then iterates over the input string and in each iteration reduce the frequency of the current character in the freq array and increase the frequency of the current character in the temp array.
• After that, initializes two variables cnt1 and cnt2 to 0 and iterate over both the freq and temp arrays to count the number of non-zero values in each array.
• If cnt1 and cnt2 are equal, it means that the input string can be split into two parts such that they have the same number of distinct letters, and the function returns True. 
• If it’s not possible to split the string into two parts such that they have the same number of distinct letters, the function returns False.

Below is the implementation of the above approach. 

Time Complexity: O(N*26), where N represents the size of the given string and 26 for the inner loop.
Auxiliary Space: O(N), where N represents the size of the freq and temp array.