algoadvance

Leetcode Problem #1957: Delete Characters to Make Fancy String

Given a string s, a fancy string is a string where no three consecutive characters are equal. Return the longest possible fancy string that can be obtained by deleting some characters from s.

Example:

Constraints:

Clarifying Questions

  1. Can the input string s be empty?
    • No, per the constraints, the length of s is at least 1.
  2. Are we allowed to manipulate the input string in place?
    • Modifying in place is not necessary. We can use additional space if needed.
  3. Are there any restrictions on the characters in s?
    • The string s contains only lowercase English letters.

Strategy

  1. Use a list to build the resulting fancy string. We will append characters from s to this list while ensuring no three consecutive characters are the same.
  2. Iterate through the input string s while simultaneously filling the resultant list based on the fancy string criterion.
  3. For each character s[i]:
    • Check if the last two characters in the resultant list are the same as s[i].
    • If they are not, append s[i] to the resultant list.
    • If they are same, skip s[i].
  4. After iterating through the input string, join the resultant list to form the final fancy string and return it.

Code

Here is the implementation of the above approach:

def makeFancyString(s: str) -> str:
    if len(s) < 3:
        return s
    
    result = []  # Initialize an empty list to store the resultant fancy string characters
    
    # Iterate through the given string
    for char in s:
        # Check if last two characters in the result list are the same as the current character
        if len(result) < 2 or not (result[-1] == char and result[-2] == char):
            result.append(char)  # append the current character if the condition is satisfied
    
    return ''.join(result)  # Convert list to string

# Example usage:
print(makeFancyString("leeetcode"))  # Output: "leetcode"
print(makeFancyString("aaabaaaa"))   # Output: "aabaa"
print(makeFancyString("aab"))        # Output: "aab"

Time Complexity

By following the above methodology, we ensure the resultant string is the longest possible fancy string as required.

Try our interview co-pilot at AlgoAdvance.com