Leetcode Daily Question 01/11/2024 - 1957. Delete Characters to Make Fancy String

Problem Description:

A fancy string is a string where no three consecutive characters are equal. | --------------------------------------------------------- | Given a string s, delete the minimum possible number of characters from s to make it fancy. | --------------------------------------------------------- | Return the final string after the deletion. It can be shown that the answer will always be unique.

class Solution:
  def makeFancyString(self, s: str) -> str:
    result = [s[0]]
    count = 1
    for i in range(1, len(s)):
      if s[i] == s[i-1]:
        count += 1
      else:
        count = 1
      
      if count < 3:
        result.append(s[i])
    
    return "".join(result)

Explanation:

We use a greedy approach to solve this. We keep a count variable to keep track of same consecutive character occurrences.

As long as we do not have the same character 3 times, we append it to our temporary array. Every time we see a distinct character, we reset the count to 1.

To finish, we join the array together using Python's in-built join() method.

def makeFancyString(s):
  result = [s[0]]
  count = 1
  for i in range(1, len(s)):
    if s[i] == s[i-1]:
      count += 1
    else:
      count = 1
    
    if count < 3:
      result.append(s[i])
    
  return "".join(result)

The time complexity is O(n) as we need to iterate through the string to construct our string.

The space complexity is O(n) as in the worst case, we need every character of s to be in our result.

The full solution can be found near the top of the page.

I added a Go implementation below for practice purposes.

package main

import (
  "fmt"
)

func makeFancyString (s string) string {
  count := int(1)
  result := []byte{s[0]}
  
  for i := 1; i < len(s); i++ {
    if s[i] == s[i-1] {
      count++
    } else {
      count = 1
    }
    
    if count < 3 { 
      result = append(result, s[i])
    }
  }
  return string(result)
}

func main () {
  s := "leeeetcode"
  fmt.Println(makeFancyString(s))
}