Number of Positions to partition the string such that atleast m characters with same frequency are present in each substring
Given a string str of lowercase English alphabets and an integer m. The task is to count how many positions are there in the string such that if you partition the string into two non-empty sub-strings, there are at least m characters with the same frequency in both sub-strings.
The characters need to be present in the string str.
Examples:
Input: str = “aabbccaa”, m = 2
Output: 2
The string has length 8, so there are 7 positions available to perform the partition.
i.e. a|a|b|b|c|c|a|a
Only two partitions are possible which satisfy the given constraints.
aab|bccaa – On the left half of the separator, ‘a’ has frequency 2 and ‘b’ has frequency 1
which is same as that of the right half.
aabbc|caa – On the left half of the separator, ‘a’ has frequency 2 and ‘c’ has frequency 1
which is same as that of the right half.
Input: str = “aabbaa”, m = 2
Output: 1
Approach: For each partition position, calculate the frequencies of each of the characters of the string in both the partitions. Then calculate the number of characters having same frequency in both partitions. If the count of such characters is at least m then add 1 to the required count of partitions.
Below is the implementation of the above approach:
// Java implementation of the approach
import java.util.*;
class GFG {
// Function to return the number of ways
// to partition the given so that the
// given condition is satisfied
static int countWays(String str, int m)
{
// Hashset to store unique characters
// in the given string
HashSet<Character> set = new HashSet<Character>();
for (int i = 0; i < str.length(); i++)
set.add(str.charAt(i));
// To store the number of ways
// to partition the string
int result = 0;
for (int i = 1; i < str.length(); i++) {
// Hashmaps to store frequency of characters
// of both the partitions
HashMap<Character, Integer> first_map
= new HashMap<Character, Integer>();
HashMap<Character, Integer> second_map
= new HashMap<Character, Integer>();
// Iterate in the first partition
for (int j = 0; j < i; j++) {
// If character already exists in the hashmap
// then increase it's frequency
if (first_map.containsKey(str.charAt(j)))
first_map.put(str.charAt(j),
(first_map.get(str.charAt(j)) + 1));
// Else create an entry for it in the Hashmap
else
first_map.put(str.charAt(j), 1);
}
// Iterate in the second partition
for (int k = i; k < str.length(); k++) {
// If character already exists in the hashmap
// then increase it's frequency
if (second_map.containsKey(str.charAt(k)))
second_map.put(str.charAt(k),
(second_map.get(str.charAt(k)) + 1));
// Else create an entry for it in the Hashmap
else
second_map.put(str.charAt(k), 1);
}
// Iterator for HashSet
Iterator itr = set.iterator();
// To store the count of characters that have
// equal frequencies in both the partitions
int total_count = 0;
while (itr.hasNext()) {
// first_count and second_count keeps track
// of the frequencies of each character
int first_count = 0, second_count = 0;
char ch = (char)itr.next();
// Frequency of the character
// in the first partition
if (first_map.containsKey(ch))
first_count = first_map.get(ch);
// Frequency of the character
// in the second partition
if (second_map.containsKey(ch))
second_count = second_map.get(ch);
// Check if frequency is same in both the partitions
if (first_count == second_count && first_count != 0)
total_count += 1;
}
// Check if the condition is satisfied
// for the current partition
if (total_count >= m)
result += 1;
}
return result;
}
// Driver code
public static void main(String[] args)
{
String str = "aabbccaa";
int m = 2;
System.out.println(countWays(str, m));
}
}
# Python3 implementation of the approach
from collections import defaultdict
# Function to return the number of ways
# to partition the given so that the
# given condition is satisfied
def countWays(string, m):
# Hashset to store unique
# characters in the given string
Set = set()
for i in range(0, len(string)):
Set.add(string[i])
# To store the number of ways
# to partition the string
result = 0
for i in range(1, len(string)):
# Hashmaps to store frequency of
# characters of both the partitions
first_map = defaultdict(lambda:0)
second_map = defaultdict(lambda:0)
# Iterate in the first partition
for j in range(0, i):
first_map[string[j]] += 1
# Iterate in the second partition
for k in range(i, len(string)):
second_map[string[k]] += 1
# To store the count of characters that have
# equal frequencies in both the partitions
total_count = 0
for ch in Set:
# first_count and second_count keeps track
# of the frequencies of each character
first_count, second_count = 0, 0
# Frequency of the character
# in the first partition
if ch in first_map:
first_count = first_map[ch]
# Frequency of the character
# in the second partition
if ch in second_map:
second_count = second_map[ch]
# Check if frequency is same in both the partitions
if first_count == second_count and first_count != 0:
total_count += 1
# Check if the condition is satisfied
# for the current partition
if total_count >= m:
result += 1
return result
# Driver code
if __name__ == "__main__":
string = "aabbccaa"
m = 2
print(countWays(string, m))
# This code is contributed by Rituraj Jain
// C# implementation of the approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to return the number of ways
// to partition the given so that the
// given condition is satisfied
static int countWays(String str, int m)
{
// Hashset to store unique characters
// in the given string
HashSet<char> set = new HashSet<char>();
for (int i = 0; i < str.Length; i++)
set.Add(str[i]);
// To store the number of ways
// to partition the string
int result = 0;
for (int i = 1; i < str.Length; i++) {
// Hashmaps to store frequency of characters
// of both the partitions
Dictionary<char, int> first_map
= new Dictionary<char, int>();
Dictionary<char, int> second_map
= new Dictionary<char, int>();
// Iterate in the first partition
for (int j = 0; j < i; j++) {
// If character already exists in the hashmap
// then increase it's frequency
if (first_map.ContainsKey(str[j]))
first_map[str[j]] =
(first_map[str[j]] + 1);
// Else create an entry for it in the Hashmap
else
first_map.Add(str[j], 1);
}
// Iterate in the second partition
for (int k = i; k < str.Length; k++) {
// If character already exists in the hashmap
// then increase it's frequency
if (second_map.ContainsKey(str[k]))
second_map[str[k]] =
(second_map[str[k]] + 1);
// Else create an entry for it in the Hashmap
else
second_map.Add(str[k], 1);
}
// To store the count of characters that have
// equal frequencies in both the partitions
int total_count = 0;
// Iterator for HashSet
foreach (int itr in set) {
// first_count and second_count keeps track
// of the frequencies of each character
int first_count = 0, second_count = 0;
char ch = (char)itr;
// Frequency of the character
// in the first partition
if (first_map.ContainsKey(ch))
first_count = first_map[ch];
// Frequency of the character
// in the second partition
if (second_map.ContainsKey(ch))
second_count = second_map[ch];
// Check if frequency is same in both the partitions
if (first_count == second_count && first_count != 0)
total_count += 1;
}
// Check if the condition is satisfied
// for the current partition
if (total_count >= m)
result += 1;
}
return result;
}
// Driver code
public static void Main(String[] args)
{
String str = "aabbccaa";
int m = 2;
Console.WriteLine(countWays(str, m));
}
}
// This code is contributed by Rajput-Ji
// Javascript implementation of the approach
// Function to return the number of ways
// to partition the given so that the
// given condition is satisfied
function countWays(str, m)
{
// Hashset to store unique characters
// in the given string
var s = new Set();
for (var i = 0; i < str.length; i++)
s.add(str[i]);
// To store the number of ways
// to partition the string
var result = 0;
for (var i = 1; i < str.length; i++)
{
// Hashmaps to store frequency of characters
// of both the partitions
var first_map = new Map(), second_map = new Map();
// Iterate in the first partition
for (var j = 0; j < i; j++)
// If character already exists in the hashmap
// then increase it's frequency
if(first_map.has(str[j]))
first_map.set(str[j], first_map.get(str[j])+1)
else
first_map.set(str[j], 1)
// Iterate in the second partition
for (var k = 0; k < str.length; k++)
// If character already exists in the hashmap
// then increase it's frequency
if(second_map.has(str[k]))
second_map.set(str[k], second_map.get(str[k])+1)
else
second_map.set(str[k], 1)
// To store the count of characters that have
// equal frequencies in both the partitions
var total_count = 0;
s.forEach(itr => {
// first_count and second_count keeps track
// of the frequencies of each character
var first_count = 0, second_count = 0;
var ch = itr;
// Frequency of the character
// in the first partition
if (first_map.has(ch))
first_count = first_map.get(ch);
// Frequency of the character
// in the second partition
if (second_map.has(ch))
second_count = second_map.get(ch);
// Check if frequency is same
// in both the partitions
if (first_count == second_count &&
first_count != 0)
total_count += 1;
});
// Check if the condition is satisfied
// for the current partition
if (total_count >= m)
result += 1;
}
return result;
}
// Driver code
var str = "aabbccaa";
var m = 2;
console.log( countWays(str, m));
// This code is contributed by itsok.
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number of ways
// to partition the given so that the
// given condition is satisfied
int countWays(string str, int m)
{
// Hashset to store unique characters
// in the given string
set<char> s;
for (int i = 0; i < str.length(); i++)
s.insert(str[i]);
// To store the number of ways
// to partition the string
int result = 0;
for (int i = 1; i < str.length(); i++)
{
// Hashmaps to store frequency of characters
// of both the partitions
map<char, int> first_map, second_map;
// Iterate in the first partition
for (int j = 0; j < i; j++)
// If character already exists in the hashmap
// then increase it's frequency
first_map[str[j]]++;
// Iterate in the second partition
for (int k = 0; k < str.length(); k++)
// If character already exists in the hashmap
// then increase it's frequency
second_map[str[k]]++;
// Iterator for HashSet
set<char>::iterator itr = s.begin();
// To store the count of characters that have
// equal frequencies in both the partitions
int total_count = 0;
while (++itr != s.end())
{
// first_count and second_count keeps track
// of the frequencies of each character
int first_count = 0, second_count = 0;
char ch = *(itr);
// Frequency of the character
// in the first partition
if (first_map.find(ch) != first_map.end())
first_count = first_map[ch];
// Frequency of the character
// in the second partition
if (second_map.find(ch) != second_map.end())
second_count = second_map[ch];
// Check if frequency is same
// in both the partitions
if (first_count == second_count &&
first_count != 0)
total_count += 1;
}
// Check if the condition is satisfied
// for the current partition
if (total_count >= m)
result += 1;
}
return result;
}
// Driver code
int main(int argc, char const *argv[])
{
string str = "aabbccaa";
int m = 2;
cout << countWays(str, m) << endl;
return 0;
}
// This code is contributed by
// sanjeev2552
Output
2
Time Complexity: O(n*n*log(n)), as nested loops are used for iteration
Auxiliary Space: O(n), as extra space of size n is used to make a set and map
Approach: Efficient Cumulative Frequency Counting
To solve the problem of partitioning the string such that at least m characters have the same frequency in both substrings, we can employ an optimized approach using cumulative frequency counting. Instead of recalculating the frequencies from scratch for every partition, we utilize prefix and suffix frequency tables. This reduces the complexity by avoiding redundant recalculations and directly comparing precomputed frequency values.
Follow the steps to solve the above problem:
- For each character at each position in the string, maintain a cumulative count of how many times that character has appeared from the start up to that position.
- Similarly, maintain a count for each character from the end of the string up to that position.
- For each possible partition point, compare the prefix frequency up to that point with the suffix frequency from that point to the end of the string.
- Count how many characters have the same frequency in both the prefix and suffix.
- For each partition point, if the number of characters with matching frequencies in both partitions is greater than or equal to m, increment the valid partition counter.
Below is the implementation of above approach:
#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
// Function to count the number of partitions satisfying the
// condition
int countPartitions(const std::string& s, int m)
{
int n = s.size();
if (n == 0) {
return 0;
}
// Initialize prefix and suffix frequency tables
std::vector<std::unordered_map<char, int> > prefixFreq(
n);
std::vector<std::unordered_map<char, int> > suffixFreq(
n);
// Fill prefix frequency table
prefixFreq[0][s[0]]++;
for (int i = 1; i < n; ++i) {
prefixFreq[i]
= prefixFreq[i - 1]; // Copy previous prefix
// frequency table
prefixFreq[i][s[i]]++; // Update the frequency of
// the current character
}
// Fill suffix frequency table
suffixFreq[n - 1][s[n - 1]]++;
for (int i = n - 2; i >= 0; --i) {
suffixFreq[i]
= suffixFreq[i + 1]; // Copy next suffix
// frequency table
suffixFreq[i][s[i]]++; // Update the frequency of
// the current character
}
// Count valid partitions
int validPartitions = 0;
for (int i = 0; i < n - 1; ++i) {
int matchCount = 0;
// Check each character in the set of all characters
// seen so far
std::unordered_set<char> checkedChars;
for (auto& entry : prefixFreq[i]) {
checkedChars.insert(entry.first);
}
for (auto& entry : suffixFreq[i + 1]) {
checkedChars.insert(entry.first);
}
for (char ch : checkedChars) {
// Increment match count if frequencies of
// character match in both prefix and suffix
if (prefixFreq[i][ch]
== suffixFreq[i + 1][ch]) {
matchCount++;
}
}
if (matchCount >= m) {
validPartitions++;
}
}
return validPartitions;
}
int main()
{
std::cout << countPartitions("aabbccaa", 2)
<< std::endl; // Output: 2
return 0;
}
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class CountPartitions {
public static int countPartitions(String s, int m)
{
int n = s.length();
if (n == 0) {
return 0;
}
// Initialize prefix and suffix frequency tables
Map<Character, Integer>[] prefixFreq
= new HashMap[n];
Map<Character, Integer>[] suffixFreq
= new HashMap[n];
// Fill prefix frequency table
prefixFreq[0] = new HashMap<>();
prefixFreq[0].put(s.charAt(0), 1);
for (int i = 1; i < n; ++i) {
prefixFreq[i] = new HashMap<>(
prefixFreq[i - 1]); // Copy previous prefix
// frequency table
prefixFreq[i].put(
s.charAt(i),
prefixFreq[i].getOrDefault(s.charAt(i), 0)
+ 1); // Update frequency
}
// Fill suffix frequency table
suffixFreq[n - 1] = new HashMap<>();
suffixFreq[n - 1].put(s.charAt(n - 1), 1);
for (int i = n - 2; i >= 0; --i) {
suffixFreq[i] = new HashMap<>(
suffixFreq[i + 1]); // Copy next suffix
// frequency table
suffixFreq[i].put(
s.charAt(i),
suffixFreq[i].getOrDefault(s.charAt(i), 0)
+ 1); // Update frequency
}
// Count valid partitions
int validPartitions = 0;
for (int i = 0; i < n - 1; ++i) {
int matchCount = 0;
// Check each character in the set of all
// characters seen so far
Set<Character> checkedChars
= new HashSet<>(prefixFreq[i].keySet());
checkedChars.addAll(suffixFreq[i + 1].keySet());
for (char ch : checkedChars) {
// Increment match count if frequencies of
// character match in both prefix and suffix
if (prefixFreq[i]
.getOrDefault(ch, 0)
.equals(
suffixFreq[i + 1].getOrDefault(
ch, 0))) {
matchCount++;
}
}
if (matchCount >= m) {
validPartitions++;
}
}
return validPartitions;
}
public static void main(String[] args)
{
System.out.println(
countPartitions("aabbccaa", 2)); // Output: 2
}
}
// This code is contributed by Shivam Gupta
def count_partitions(s, m):
from collections import defaultdict
n = len(s)
if n == 0:
return 0
# Initialize prefix and suffix frequency tables
prefix_freq = [defaultdict(int) for _ in range(n)]
suffix_freq = [defaultdict(int) for _ in range(n)]
# Fill prefix frequency table
prefix_freq[0][s[0]] += 1
for i in range(1, n):
prefix_freq[i] = prefix_freq[i - 1].copy()
prefix_freq[i][s[i]] += 1
# Fill suffix frequency table
suffix_freq[n - 1][s[n - 1]] += 1
for i in range(n - 2, -1, -1):
suffix_freq[i] = suffix_freq[i + 1].copy()
suffix_freq[i][s[i]] += 1
# Count valid partitions
valid_partitions = 0
for i in range(n - 1):
match_count = 0
# Check each character in the set of all characters seen so far
checked_chars = set(prefix_freq[i].keys()).union(
suffix_freq[i + 1].keys())
for ch in checked_chars:
if prefix_freq[i].get(ch, 0) == suffix_freq[i + 1].get(ch, 0):
match_count += 1
if match_count >= m:
valid_partitions += 1
return valid_partitions
# Example usage:
print(count_partitions("aabbccaa", 2)) # Output: 2
function countPartitions(s, m) {
const n = s.length;
if (n === 0) return 0;
// Initialize prefix and suffix frequency tables
let prefixFreq = Array.from({ length: n }, () => ({}));
let suffixFreq = Array.from({ length: n }, () => ({}));
// Fill prefix frequency table
prefixFreq[0][s[0]] = 1;
for (let i = 1; i < n; ++i) {
prefixFreq[i] = { ...prefixFreq[i - 1] };
prefixFreq[i][s[i]] = (prefixFreq[i][s[i]] || 0) + 1;
}
// Fill suffix frequency table
suffixFreq[n - 1][s[n - 1]] = 1;
for (let i = n - 2; i >= 0; --i) {
suffixFreq[i] = { ...suffixFreq[i + 1] };
suffixFreq[i][s[i]] = (suffixFreq[i][s[i]] || 0) + 1;
}
// Count valid partitions
let validPartitions = 0;
for (let i = 0; i < n - 1; ++i) {
let matchCount = 0;
// Get all unique characters seen so far in prefix and suffix
const checkedChars = new Set([...Object.keys(prefixFreq[i]), ...Object.keys(suffixFreq[i + 1])]);
// Check each character in the set of all characters seen so far
for (let ch of checkedChars) {
if ((prefixFreq[i][ch] || 0) === (suffixFreq[i + 1][ch] || 0)) {
matchCount++;
}
}
if (matchCount >= m) {
validPartitions++;
}
}
return validPartitions;
}
// Example usage:
console.log(countPartitions("aabbccaa", 2)); // Output: 2
Output
2
Time Complexity: O(n *k), where k is typically much smaller than n and limited to 26 for lowercase English letters.
Space Complexity: O(n x k) for storing the frequency of each character at each position in the prefix and suffix tables.
Contact Us