Maximum consecutive repeating character in string in Java
The maximum consecutive repeating character in a string is a common challenge in string manipulation and algorithmic problem-solving. It involves analyzing a string and identifying the character that appears consecutively for the longest continuous sequence. The algorithmic task has applications in data analysis, text processing, and understanding genetic sequences in natural language.
Example 1:
Input: “aabbcccdd”
Output: c
Explanation: The character "c" appears consecutively for the longest continuous sequence in the given string, "aabbcccdd." It repeats itself three times in a row, making it the longest consecutive repeating sequence. Thus, "c" is the output.
Using Naive Approach
The naive approach defines a class `MaxConsecutiveRepeatingChar` with two methods: `findMaxConsecutiveRepeatingChar` and `main`. The `findMaxConsecutiveRepeatingChar` method uses a nested loop to iterate through a string, counting consecutive occurrences of each character and updating the result when a longer consecutive sequence is found. The main method initializes a string `input` with the value "aaabbccccddddd", calls the `findMaxConsecutiveRepeatingChar` method, and prints the result to the console.
Here’s an implementation of a maximum consecutive repeating character in a string using a naive approach :
FileName: MaxConsecutiveRepeatingChar.java
public class MaxConsecutiveRepeatingChar {
// Function to find the maximum consecutive repeating character in a string
public static char findMaxConsecutiveRepeatingChar(String str) {
char result = '\0'; // Variable to store the result
int maxCount = 0; // Variable to store the maximum consecutive count
for (int i = 0; i < str.length(); i++) {
char currentChar = str.charAt(i);
int currentCount = 1; // Count of consecutive occurrences of the current character
for (int j = i + 1; j < str.length(); j++) {
if (str.charAt(j) == currentChar) {
currentCount++;
} else {
break;
}
}
// Update the result if the current count is greater than the maximum count
if (currentCount > maxCount) {
maxCount = currentCount;
result = currentChar;
}
}
return result;
}
public static void main(String[] args) {
String input = "aaabbccccddddd";
char maxConsecutiveChar = findMaxConsecutiveRepeatingChar(input);
System.out.println("Maximum consecutive repeating character: " + maxConsecutiveChar);
}
}
Output:
Maximum consecutive repeating character: d
Complexity analysis: The code has a time complexity of O(n^2) due to nested loops, with the outer loop running 'n' times and the inner loop counting consecutive occurrences of the current character. The space complexity is O(1), as the algorithm's additional memory doesn't depend on the input string size. The quadratic time complexity suggests the algorithm may become inefficient for large input strings, necessitating more efficient linear or near-linear time complexity solutions.
Using Optimized Approach
The optimized approach aims to find the maximum consecutive repeating character in a string while minimizing computations. The code initializes variables `result`, `maxCount`, and `currentCount` and uses a single loop to traverse the input string from index 1 to `str.length() - 1`. It checks if each character is equal to the previous one, increments `currentCount` if equal, and resets `currentCount` if not. The algorithm updates the `result` only when a longer consecutive sequence is encountered, resulting in a more efficient algorithm with a linear time complexity.
Here’s an implementation of a maximum consecutive repeating character in a string using an optimized approach :
FileName: MaxConsecutiveRepeatingChar1.java
public class MaxConsecutiveRepeatingChar1 {
// Function to find the maximum consecutive repeating character in a string
public static char findMaxConsecutiveRepeatingChar(String str) {
char result = '\0'; // Variable to store the result
int maxCount = 0; // Variable to store the maximum consecutive count
int currentCount = 1; // Variable to store the current consecutive count
for (int i = 1; i < str.length(); i++) {
// Check if the current character is equal to the previous character
if (str.charAt(i) == str.charAt(i - 1)) {
currentCount++;
} else {
currentCount = 1; // Reset the current consecutive count for a new sequence
}
// Update the result if the current count is greater than the maximum count
if (currentCount > maxCount) {
maxCount = currentCount;
result = str.charAt(i);
}
}
// Check for the last character sequence
if (currentCount > maxCount) {
maxCount = currentCount;
result = str.charAt(str.length() - 1);
}
return result;
}
public static void main(String[] args) {
String input = "aaabbccccddddd";
char maxConsecutiveChar = findMaxConsecutiveRepeatingChar(input);
System.out.println("Maximum consecutive repeating character: " + maxConsecutiveChar);
}
}
Output:
Maximum consecutive repeating character: d
Complexity analysis: The optimized Java code has a linear time complexity of O(n), where 'n' is the input string length. Iterating through the string once, constant-time operations are performed, and the space complexity is O(1), constant. That improves efficiency, especially for large input strings, by avoiding unnecessary nested loops and performing a single pass through the input.
Using the Sliding Window Approach
The sliding window approach is a method to efficiently process arrays or sequences by maintaining a window of elements that move through the sequence. It optimizes computations by updating the window at each step rather than recomputing the entire solution for each position. In the context of finding the maximum consecutive repeating character in a string, the sliding window approach involves initializing variables, iterating through the string, updating the result, checking for the last window, and returning the final value of the result. The above method minimizes unnecessary comparisons and efficiently identifies the maximum consecutive repeating character with a linear time complexity.
Here’s an implementation of a maximum consecutive repeating character in a string using a sliding window approach :
FileName: MaxConsecutiveRepeatingChar2.java
public class MaxConsecutiveRepeatingChar {
// Function to find the maximum consecutive repeating character in a string
public static char findMaxConsecutiveRepeatingChar(String str) {
if (str == null || str.isEmpty()) {
return '\0';
}
char result = str.charAt(0);
int maxCount = 1;
int currentCount = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == str.charAt(i - 1)) {
currentCount++;
} else {
currentCount = 1; // Reset the current consecutive count for a new sequence
}
// Update the result if the current count is greater than the maximum count
if (currentCount > maxCount) {
maxCount = currentCount;
result = str.charAt(i);
}
}
return result; }
public static void main(String[] args) {
String input = "aaabbccccddddd";
char maxConsecutiveChar = findMaxConsecutiveRepeatingChar(input);
System.out.println("Maximum consecutive repeating character: " + maxConsecutiveChar);
}
}
Output:
Maximum consecutive repeating character: d
Complexity analysis: The sliding window approach is a method for finding the maximum consecutive repeating character in a string. Its time complexity is generally O(n), where n is the input sequence length. The algorithm processes each element once, performing constant-time operations at each step. The space complexity varies depending on the implementation but is usually O(1) or constant. The method is favoured for efficiency, especially when solving problems involving contiguous subarrays or consecutive sequences.