Minimum characters that are to be inserted such that no three consecutive characters are same in Java
The problem is modifying a string by adding characters so that no three consecutive characters are identical.
Example
Input: aaabbbcc
Output: 2
Explanation: In the input string, "aaa" and "bbb" are three consecutive identical characters. To break the pattern, characters are placed between the second and third characters in each sequence, yielding the output string "aabababbcc", in which no three consecutive characters are identical.
Iterative Approach
Algorithm
Step 1: Start with the input string "aaabbbcc".
Step 2: Iterate through the string, checking for consecutive sequences of three identical characters.
Step 3: Upon finding such a sequence, insert a different character between the second and third characters to break the sequence.
Step 4: Repeat the process until no more consecutive sequences of three identical characters exist.
FileName: NoThreeConsecutiveCharacters.java
public class NoThreeConsecutiveCharacters { public static int insertCharactersIterative(String input) { StringBuilder output = new StringBuilder(input); int count = 0; // Variable to count the number of insertions // Iterate through the string to find consecutive sequences for (int i = 0; i < output.length() - 2; i++) { if (output.charAt(i) == output.charAt(i + 1) && output.charAt(i) == output.charAt(i + 2)) { // Insert a different character between the second and third characters char newChar = generateDifferentCharacter(output.charAt(i), output.charAt(i + 1)); output.insert(i + 2, newChar); count++; // Increment count for each insertion } } return count; } private static char generateDifferentCharacter(char c1, char c2) { char candidate = 'a'; // Find a character that is different from c1 and c2 while (candidate == c1 || candidate == c2) { candidate++; } return candidate; } public static void main(String[] args) { String input = "aaabbbcc"; int result = insertCharactersIterative(input); System.out.println(insertCharactersIterative(input)); } }
Output:
2
Complexity Analysis: The time complexity of the code is O(n) where n is the length of the input string and the space complexity is O(n).
Recursive Approach
Algorithm
Step 1: Start with the input string "aaabbbcc".
Step 2: Implement a recursive function to check for consecutive sequences of three identical characters.
Step 3: Upon finding such a sequence, insert a different character between the second and third characters to break the sequence.
Step 4: Recursively call the function until no more consecutive sequences of three identical characters exist.
FileName: NoThreeConsecutiveCharacters1.java
public class NoThreeConsecutiveCharacters1 { public static int insertCharactersRecursive(String input) { StringBuilder output = new StringBuilder(input); int count = insertCharactersRecursiveHelper(output); return count; } private static int insertCharactersRecursiveHelper(StringBuilder output) { int count = 0; // Variable to count the number of insertions // Iterate through the string to find consecutive sequences for (int i = 0; i < output.length() - 2; i++) { if (output.charAt(i) == output.charAt(i + 1) && output.charAt(i) == output.charAt(i + 2)) { // Insert a different character between the second and third characters char newChar = generateDifferentCharacter(output.charAt(i), output.charAt(i + 1)); output.insert(i + 2, newChar); count++; // Increment count for each insertion // Recursively call the function with the modified string count += insertCharactersRecursiveHelper(output); break; // Exit loop after one insertion } } return count; } private static char generateDifferentCharacter(char c1, char c2) { char candidate = 'a'; // Find a character that is different from c1 and c2 while (candidate == c1 || candidate == c2) { candidate++; } return candidate; } public static void main(String[] args) { String input = "aaabbbcc"; int result = insertCharactersRecursive(input); System.out.println(insertCharactersRecursive(input)); } }
Output:
2
Complexity Analysis: The time complexity of the code is O(n^2) where n is the length of the input string and the space complexity is O(n).
Regular Expression Approach
Algorithm
Step 1: Start with the input string "aaabbbcc".
Step 2: Define a regular expression pattern to match any sequence of three consecutive identical characters.
Step 3: Use the Matcher class to find all matches of the pattern in the input string.
Step 4: For each match found, insert a different character between the second and third characters to break the sequence.
Step 5: Increment a count variable for each insertion made.
Step 6: Continue replacing matches until no more consecutive sequences of three identical characters are found.
Step 7: Return the count of insertions made and the modified string.
FileName: NoThreeConsecutiveCharacters2.java
import java.util.regex.Matcher; import java.util.regex.Pattern; public class NoThreeConsecutiveCharacters2 { public static int insertCharactersRegex(String input) { // Define the pattern for three consecutive identical characters Pattern pattern = Pattern.compile("(.)\1{2}"); Matcher matcher = pattern.matcher(input); int count = 0; // Variable to count the number of insertions // Replace each match with a modified substring StringBuffer result = new StringBuffer(); while (matcher.find()) { char newChar = generateDifferentCharacter(matcher.group().charAt(0), matcher.group().charAt(1)); matcher.appendReplacement(result, "$1" + newChar); count++; // Increment count for each insertion } matcher.appendTail(result); return count; } private static char generateDifferentCharacter(char c1, char c2) { char candidate = 'a'; // Find a character that is different from c1 and c2 while (candidate == c1 || candidate == c2) { candidate++; } return candidate; } public static void main(String[] args) { String input = "aaabbbcc"; int result = insertCharactersRegex(input); System.out.println(insertCharactersRegex(input)); } }
Output:
2
Complexity Analysis: The time complexity and space complexity the code is O(m+n), where m is the length of the pattern and n is the length of the input string.