Replace All S To Avoid Consecutive Repeating Characters - Leetcode Solution

Problem Overview:

Given a string s consisting only of lowercase letters 'a' to 'z'. We have to replace every occurrence of letter 's' in the string with one of the letters in the set {'a', 'b', 'c'}, so that there are no consecutive repeating characters in the resulting string. The final resulting string after performing the replacement operations needs to be returned.

Example:

Input: s = "abbcaaa" Output: "abcbcac"

Solution:

The problem can be solved by iterating over the string s and replacing each 's' with some character from {'a', 'b', 'c'}. We replace the letter 's' with the first character from {'a', 'b', 'c'} which is different from its adjacent characters. If there is no such character left in the set, then it means it is not possible to replace 's' without having consecutive repeating characters. Thus, we return an empty string.

Algorithm:

1. Define a set of characters S as {'a', 'b', 'c'}.
2. Initialize an empty string result.
3. Iterate over the string s from left to right using a loop.
4. If the current character is 's', then replace it with the first character in S, which is different from its adjacent characters in the resulting string 'result'. If no such character exists, then return an empty string, as it is not possible to replace 's' without consecutive repeating characters.
5. If the current character is not 's', then append it to the string 'result'.
6. Return the final resulting string 'result'.

Code:

class Solution: def modifyString(self, s: str) -> str: S = set(['a', 'b', 'c']) n = len(s) res = ''

    for i in range(n):
        if s[i] == 's':
            for c in S:
                if (i == 0 or c != res[i-1]) and (i == n-1 or c != s[i+1]):
                    res += c
                    break
            else:
                return ''
        else:
            res += s[i]
            
    return res 

Time Complexity: O(n), where n is the length of the given string s.

Space Complexity: O(1), as we are not using any extra space proportional to the input size.

1