algoadvance

Leetcode 1576. Replace All ?’s to Avoid Consecutive Repeating Characters

Problem Statement

Given a string s containing only lowercase English letters and the '?' character, you need to replace every '?' character with a lowercase English letter so that the final string does not contain any consecutive repeating characters. You can assume that the given string is not too long and that it is always possible to replace the '?' character to achieve the desired outcome.

Clarifying Questions

1. Input Constraints:
   • Can s be empty? Answer: Yes, it can be. An empty string should return as it is.
   • What is the maximum length of s? Answer: It can be reasonably long, but we won’t specify exact limits here as the problem assumes it won’t be too long.
2. Output:
   • We should return any valid output string that fulfills the non-repeating condition.

Strategy

1. Iterate Through String:
   • Loop through the string, and when a '?' is found, choose a replacement character.
2. Choosing a Replacement Character:
   • The replacement character should not match either the character before or after it (if they exist).
3. Implementation:
   • Convert the string to a character array for easy manipulation.
   • For each '?' encountered, choose a character from ‘a’ to ‘z’ ensuring it doesn’t create a repeating sequence.
4. Edge Cases:
   • Handle the first and last characters carefully since they don’t have both neighbors.
   • Handle consecutive '?' characters correctly by processing them from left to right.

Code

public class ReplaceQuestionMarks {

    public static String modifyString(String s) {
        char[] charArray = s.toCharArray();
        int n = charArray.length;
        
        for (int i = 0; i < n; i++) {
            if (charArray[i] == '?') {
                for (char replacement = 'a'; replacement <= 'z'; replacement++) {
                    if ((i > 0 && charArray[i - 1] == replacement) || (i < n - 1 && charArray[i + 1] == replacement)) {
                        continue;
                    }
                    charArray[i] = replacement;
                    break;
                }
            }
        }
        return new String(charArray);
    }

    public static void main(String[] args) {
        // Example test cases
        System.out.println(modifyString("ab?ac"));  // Sample input
        System.out.println(modifyString("??ywz"));  // Sample input
        System.out.println(modifyString("a?b?c"));  // Sample input
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the input string s. This is because we only make a single pass through the string and each character replacement operation takes constant time.
• Space Complexity: O(n), where n is the length of the input string s. This is due to storing the character array and eventually converting it back to a string.

By following this approach, we ensure that we do not introduce any consecutive repeating characters while replacing all '?' characters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?