Number of Equal Count Substrings in Java
Given a string s. If a substring of s has every unique letter exactly count times in the substring, the substring is said to be equal count substring. The task is to return the number of equal count substrings in s.
Example 1
Input: s = “abc”, count = 2
Output: 0
Explanation: There are no substrings where any character appears exactly 2 times.
Example 2
Input: s = "aaabcbbcc", count = 3
Output: 3
Explanation: The substrings "aaa", "bcbbcc", and "aaabcbbcc" have characters appearing exactly 3 times each.
Approach 1: Using Brute Force
The brute force approach is used to find the number of substrings in which each character appears exactly a specified number of times (denoted by count). This is achieved by examining all possible substrings and using a frequency map to count the occurrences of each character in the substring.
Algorithm
Step 1: Iterate through each possible starting index of the substring.
Step 2: For each starting index, iterate through each possible ending index to form substrings.
Step 3: Use a frequency map to count occurrences of each character in the current substring.
Step 4: Check if all characters in the frequency map have the specified count.
Step 5: If they do, increment the result counter.
Step 6: Return the result counter after all substrings have been checked.
FileName: EqualCountSubstringsBruteForce.java
import java.util.HashMap; import java.util.Map; public class EqualCountSubstringsBruteForce { public static void main(String[] args) { String s = "aaabcbbcc"; int count = 3; System.out.println(countEqualCountSubstrings(s, count)); } public static int countEqualCountSubstrings(String s, int count) { int n = s.length(); // Length of the input string int result = 0; // Variable to store the number of valid substrings // Iterate through each possible starting index of the substring for (int start = 0; start < n; start++) { MapfreqMap = new HashMap<>(); // Frequency map to count occurrences of each character // Iterate through each possible ending index to form substrings for (int end = start; end < n; end++) { char currentChar = s.charAt(end); // Current character in the substring freqMap.put(currentChar, freqMap.getOrDefault(currentChar, 0) + 1); // Update the frequency map // Check if the current character has reached the specified count if (freqMap.get(currentChar) == count) { boolean allEqual = true; // Flag to check if all characters have the specified count // Check if all characters in the frequency map have the specified count for (int val : freqMap.values()) { if (val != count) { allEqual = false; break; } } // If all characters have the specified count, increment the result counter if (allEqual) { result++; } } else if (freqMap.get(currentChar) > count) { // If any character exceeds the specified count, break the loop break; } } } return result; // Return the number of valid substrings } }
Output
3
Time Complexity: The time complexity of an algorithm is O(n^3). This is because the outer loop runs O(n) times for each starting index and the inner loop runs O(n) times for each ending index and the check for all characters having the specified count runs O(n) times in the worst case, where n is the length of the string.
Space Complexity: The space complexity of an algorithm is O(n). This is because the frequency map can store up to n characters.
Approach 2: Sliding Window
A sliding window technique combined with a frequency map to efficiently count the number of substrings where each character appears exactly count times.
Algorithm
Step 1: Iterate through each possible starting index of the substring.
Step 2: Use a frequency map to count occurrences of each character in the current window.
Step 3: Track the number of characters that have reached the desired count using validCount.
Step 4: If all characters in the frequency map have the exact count, increment the result counter.
Step 5: Return the result counter after all substrings have been checked.
FileName: EqualCountSubstringsSlidingWindow.java
import java.util.HashMap; import java.util.Map; public class EqualCountSubstringsSlidingWindow { public static void main(String[] args) { String s = "aaabcbbcc"; int count = 3; System.out.println(countEqualCountSubstrings(s, count)); // Output: 3 } public static int countEqualCountSubstrings(String s, int count) { int n = s.length(); // Length of the input string int result = 0; // Variable to store the number of valid substrings // Iterate through each possible starting index of the substring for (int start = 0; start < n; start++) { MapfreqMap = new HashMap<>(); // Frequency map to count occurrences of each character int validCount = 0; // Tracks the number of characters that have reached the specified count // Iterate through each possible ending index to form substrings for (int end = start; end < n; end++) { char currentChar = s.charAt(end); // Current character in the substring freqMap.put(currentChar, freqMap.getOrDefault(currentChar, 0) + 1); // Update the frequency map // Update validCount when a character reaches the specified count if (freqMap.get(currentChar) == count) { validCount++; } else if (freqMap.get(currentChar) == count + 1) { // Decrement validCount if it exceeds the specified count validCount--; } // If validCount matches the size of the frequency map, increment the result counter if (validCount == freqMap.size()) { result++; } } } return result; // Return the number of valid substrings } }
Output
3
Time Complexity: The time complexity of an algorithm is O(n^2). This is because the outer loop runs O(n) times for each starting index and the inner loop runs O(n) times for each ending index.
Space Complexity: The space complexity of an algorithm is O(n). This is because the frequency map can store up to n characters.