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.
C++
// C++ program to Check if a String// can be Split into good ways#include <bits/stdc++.h>using namespace std;// Function to check the splitting string// into two parts such that they have// same number of distinct lettersbool isGoodSplit(string s, int n){ // Store the frequency of // characters in string vector<int> freq(26, 0); // Count frequency of each char for (auto ch : s) freq[ch - 'a']++; // Delcare the temp array vector<int> temp(26, 0); int maxi = 0; // Iterate on string for (int i = 0; i < n; i++) { // Reduce the frequency of the // ith char from freq array freq[s[i] - 'a']--; // Increase the frequency of the // ith char in temp array temp[s[i] - 'a']++; // Initialize counts to 0 int cnt1 = 0, cnt2 = 0; // Iterate on both arrays for (int j = 0; j < 26; j++) { // Increment cnt1 if freq // array contains characters if (freq[j]) cnt1++; // Increment cnt2 if temp // array contains characters if (temp[j]) cnt2++; } // Both counts are same then it's // possible to split string if (cnt1 == cnt2) return true; } // if it's not possible return false;}// Driver Codeint main(){ string s = "abccba"; int n = s.size(); // Function call if (isGoodSplit(s, n)) { cout << "True"; } else { cout << "False"; } return 0;} |
Java
// Java program to check if a string can be split into good// waysimport java.util.*;public class GoodSplit { // Function to check the splitting string // into two parts such that they have // same number of distinct letters public static boolean isGoodSplit(String s, int n) { // Store the frequency of characters in string int[] freq = new int[26]; // Count frequency of each character for (int i = 0; i < n; i++) { freq[s.charAt(i) - 'a']++; } // Declare the temp array int[] temp = new int[26]; int maxi = 0; // Iterate on string for (int i = 0; i < n; i++) { // Reduce the frequency of the ith char from // freq array freq[s.charAt(i) - 'a']--; // Increase the frequency of the ith char in // temp array temp[s.charAt(i) - 'a']++; // Initialize counts to 0 int cnt1 = 0, cnt2 = 0; // Iterate on both arrays for (int j = 0; j < 26; j++) { // Increment cnt1 if freq array contains // characters if (freq[j] > 0) { cnt1++; } // Increment cnt2 if temp array contains // characters if (temp[j] > 0) { cnt2++; } } // Both counts are same then it's possible to // split string if (cnt1 == cnt2) { return true; } } // If it's not possible return false; } // Driver Code public static void main(String[] args) { String s = "abccba"; int n = s.length(); // Function call if (isGoodSplit(s, n)) { System.out.println("True"); } else { System.out.println("False"); } }} |
Python3
# Function to check the splitting string# into two parts such that they have# same number of distinct lettersdef isGoodSplit(s, n): # Store the frequency of # characters in string freq = [0]*26 # Count frequency of each char for c in s: freq[ord(c) - ord('a')] += 1 # Delcare the temp array temp = [0]*26 # Iterate on string for i in range(n): # Reduce the frequency of the # ith char from freq array freq[ord(s[i]) - ord('a')] -= 1 # Increase the frequency of the # ith char in temp array temp[ord(s[i]) - ord('a')] += 1 # Initialize counts to 0 cnt1, cnt2 = 0, 0 # Iterate on both arrays for j in range(26): # Increment cnt1 if freq # array contains characters if freq[j]: cnt1 += 1 # Increment cnt2 if temp # array contains characters if temp[j]: cnt2 += 1 # Both counts are same then it's # possible to split string if cnt1 == cnt2: return True # if it's not possible return False# Driver Codeif __name__ == '__main__': s = "abccba" n = len(s) # Function call if isGoodSplit(s, n): print("True") else: print("False") |
C#
// C# program to check if a string can be split into good// waysusing System;using System.Collections.Generic;class Program { static bool IsGoodSplit(string s, int n) { // Store the frequency of characters in string int[] freq = new int[26]; foreach (char c in s) { freq++; } // Delcare the temp array int[] temp = new int[26]; // Iterate on string for (int i = 0; i < n; i++) { // Reduce the frequency of the ith char from freq array freq[s[i] - 'a']--; // Increase the frequency of the ith char in temp array temp[s[i] - 'a']++; // Initialize counts to 0 int cnt1 = 0, cnt2 = 0; // Iterate on both arrays for (int j = 0; j < 26; j++) { // Increment cnt1 if freq array contains characters if (freq[j] > 0) { cnt1++; } // Increment cnt2 if temp array contains characters if (temp[j] > 0) { cnt2++; } } // Both counts are same then it's possible to split string if (cnt1 == cnt2) { return true; } } // If it's not possible return false; } static void Main(string[] args) { string s = "abccba"; int n = s.Length; // Function call if (IsGoodSplit(s, n)) { Console.WriteLine("True"); } else { Console.WriteLine("False"); } }} |
Javascript
// JavaScript program to Check if a String// can be Split into good waysfunction isGoodSplit(s, n) { // Store the frequency of characters in string let freq = new Array(26).fill(0); for (let i = 0; i < s.length; i++) { freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Delcare the temp array let temp = new Array(26).fill(0); let maxi = 0; // Iterate on string for (let i = 0; i < n; i++) { // Reduce the frequency of the ith char from freq array freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]--; // Increase the frequency of the ith char in temp array temp[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; // Initialize counts to 0 let cnt1 = 0, cnt2 = 0; // Iterate on both arrays for (let j = 0; j < 26; j++) { // Increment cnt1 if freq array contains characters if (freq[j]) cnt1++; // Increment cnt2 if temp array contains characters if (temp[j]) cnt2++; } // Both counts are same then it's possible to split string if (cnt1 == cnt2) return true; } // if it's not possible return false;}// Driver Codelet s = "abccba";let n = s.length;// Function callif (isGoodSplit(s, n)) { console.log("True");} else { console.log("False");}// This code is contributed by Prajwal Kandekar |
Output
True
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.
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
