Check if frequency of all characters can become same by one removal in Java
In this article, we will explore the topic of evaluating if it is possible to attain an equal frequency of each distinct character within a string by eliminating only one character. The string is made up entirely of lowercase alphabetic characters, and our goal is to see if, after the removal process, the remaining characters can be reorganized so that each character in the string has the same frequency.
Example 1:
Input: s= "aabbcdd”
Output: Yes
Explanation:
In the input "aabbcdd," deleting the character 'c' makes all frequencies equal.
Example 2:
Input: s= "abcddd”
Output: No
Explanation:
In this situation, no single elimination will result in equal frequencies.
Greedy Approach
To record the frequency of each lowercase English letter, the code first initializes a 26-element array called frequencyArray, which is set to zero. Following that, it counts the frequencies by iterating over each character c in the input string s and incrementing the associated frequency in frequencyArray with frequencyArray[c - 'a']++. The algorithm then determines whether all frequencies in frequencyArray are already the same, in which case it returns "Yes." If the frequencies are not uniform, the algorithm attempts to make them so by sequentially decrementing the frequency of each character in frequencyArray and testing for consistency. If the algorithm succeeds, it returns "Yes." Finally, if no solution is discovered following these steps, the program returns "No."
FileName: CharacterFrequency.java
public class CharacterFrequency {
public static String canMakeFrequencySame(String str) {
int[] frequencyArray = new int[26]; // Assuming only lowercase English letters
// Count the frequency of each character
for (char c : str.toCharArray()) {
frequencyArray[c - 'a']++;
}
// Check if all frequencies are the same
if (areFrequenciesSame(frequencyArray)) {
return "Yes";
}
// Iterate over characters and try removing each one to make frequencies same
for (int i = 0; i < 26; i++) {
if (frequencyArray[i] > 0) {
frequencyArray[i]--;
// Check if frequencies become same after removal
if (areFrequenciesSame(frequencyArray)) {
return "Yes";
}
// Restore the frequency for the next iteration
frequencyArray[i]++;
}
}
// If no solution is found, return "No"
return "No";
}
private static boolean areFrequenciesSame(int[] frequencyArray) {
// Get the first non-zero frequency
int firstFrequency = 0;
for (int frequency : frequencyArray) {
if (frequency > 0) {
firstFrequency = frequency;
break;
}
}
// Check if all frequencies are the same
for (int frequency : frequencyArray) {
if (frequency > 0 && frequency != firstFrequency) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s = "aabbcdd"; // Updated input
System.out.println(canMakeFrequencySame(s));
}
}
Output:
Yes
Complexity Analysis: The code has a time complexity of O(N), where N is the input string length and space complexity is O(1).
HashMap Approach
The Java code defines a class CharacterFrequency1, which determines if it is possible to make the frequencies of characters in a given string equal by eliminating or rearranging them. It uses a HashMap to record character frequencies, iterates through the input string to count frequencies, and attempts to make them consistent by eliminating one character at a time.
FileName: CharacterFrequency1.java
import java.util.HashMap;
import java.util.Map;
public class CharacterFrequency1 {
public static String canMakeFrequencySame(String str) {
Map<Character, Integer> frequencyMap = new HashMap<>();
// Count the frequency of each character
for (char c : str.toCharArray()) {
frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
}
// Check if all frequencies are the same
if (areFrequenciesSame(frequencyMap)) {
return "Yes";
}
// Iterate over characters and try removing each one to make frequencies same
for (char c : frequencyMap.keySet()) {
frequencyMap.put(c, frequencyMap.get(c) - 1);
// Check if frequencies become same after removal
if (areFrequenciesSame(frequencyMap)) {
return "Yes";
}
// Restore the frequency for the next iteration
frequencyMap.put(c, frequencyMap.get(c) + 1);
}
// If no solution is found, return "No"
return "No";
}
private static boolean areFrequenciesSame(Map<Character, Integer> frequencyMap) {
// Get the first non-zero frequency
int firstFrequency = 0;
for (int frequency : frequencyMap.values()) {
if (frequency > 0) {
firstFrequency = frequency;
break;
}
}
// Check if all frequencies are the same
for (int frequency : frequencyMap.values()) {
if (frequency > 0 && frequency != firstFrequency) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s = "aabbcdd"; // Updated input
System.out.println(canMakeFrequencySame(s)); // Output: Yes
}
}
Output:
Yes
Complexity Analysis: The code has a time complexity of O(N), where N is the input string length and space complexity is O(N).