Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1957.html

1957. Delete Characters to Make Fancy String

Level

Easy

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.

Example 1:

Input: s = “leeetcode”

Output: “leetcode”

Explanation:

Remove an ‘e’ from the first group of ‘e’s to create “leetcode”.

No three consecutive characters are equal, so return “leetcode”.

Example 2:

Input: s = “aaabaaaa”

Output: “aabaa”

Explanation:

Remove an ‘a’ from the first group of ‘a’s to create “aabaaaa”.

Remove two ‘a’s from the second group of ‘a’s to create “aabaa”.

No three consecutive characters are equal, so return “aabaa”.

Example 3:

Input: s = “aab”

Output: “aab”

Explanation: No three consecutive characters are equal, so return “aab”.

Constraints:

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters.

Solution

Loop over s and find the size of each group with consecutive equal characters. If a group has size less than three, than append all the characters to the result string. Otherwise, only append two of the characters to the result string. Finally, return the result string.

  • class Solution {
        public String makeFancyString(String s) {
            StringBuffer sb = new StringBuffer();
            int length = s.length();
            char prev = ' ';
            int count = 1;
            for (int i = 0; i < length; i++) {
                char curr = s.charAt(i);
                if (curr == prev)
                    count++;
                else {
                    count = 1;
                    prev = curr;
                }
                if (count < 3)
                    sb.append(curr);
            }
            return sb.toString();
        }
    }
    
    ############
    
    class Solution {
        public String makeFancyString(String s) {
            StringBuilder ans = new StringBuilder();
            for (char c : s.toCharArray()) {
                int n = ans.length();
                if (n > 1 && ans.charAt(n - 1) == c && ans.charAt(n - 2) == c) {
                    continue;
                }
                ans.append(c);
            }
            return ans.toString();
        }
    }
    
  • // OJ: https://leetcode.com/problems/delete-characters-to-make-fancy-string/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        string makeFancyString(string s) {
            int i = 0, j = 0, N = s.size();
            while (i < N) {
                int start = i;
                while (i < N && s[i] == s[start]) {
                    if (i - start < 2) s[j++] = s[i];
                    ++i;
                }
            }
            s.resize(j);
            return s;
        }
    };
    
  • class Solution:
        def makeFancyString(self, s: str) -> str:
            ans = []
            for c in s:
                if len(ans) > 1 and ans[-1] == ans[-2] == c:
                    continue
                ans.append(c)
            return ''.join(ans)
    
    ############
    
    # 1957. Delete Characters to Make Fancy String
    # https://leetcode.com/problems/delete-characters-to-make-fancy-string/
    
    class Solution:
        def makeFancyString(self, s: str) -> str:
            deque = collections.deque()
            
            for c in s:
                deque.append(c)
                
                while len(deque) >= 3 and deque[-1] == deque[-2] == deque[-3]:
                    deque.pop()
            
            return "".join(deque)
    
    
  • func makeFancyString(s string) string {
    	ans := []rune{}
    	for _, c := range s {
    		n := len(ans)
    		if n > 1 && ans[n-1] == c && ans[n-2] == c {
    			continue
    		}
    		ans = append(ans, c)
    	}
    	return string(ans)
    }
    
  • class Solution {
        /**
         * @param String $s
         * @return String
         */
        function makeFancyString($s) {
            $rs = "";
            for ($i = 0; $i < strlen($s); $i++) {
                if ($s[$i] == $s[$i + 1] && $s[$i] == $s[$i + 2]) continue;
                else $rs .= $s[$i];
            }
            return $rs;
        }
    }
    

All Problems

All Solutions