1957. Delete Characters to Make Fancy String

Problem

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.

https://leetcode.com/problems/delete-characters-to-make-fancy-string/

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⁵
• s consists only of lowercase English letters.

Test Cases

1
2

class Solution:
    def makeFancyString(self, s: str) -> str:

1
2
3
4
5
6
7
8
9
10
11
12
13

import pytest

from solution import Solution


@pytest.mark.parametrize('s, expected', [
    ("leeetcode", "leetcode"),
    ("aaabaaaa", "aabaa"),
])
class Test:
    def test_solution(self, s, expected):
        sol = Solution()
        assert sol.makeFancyString(s) == expected

Thoughts

跟 3206. Alternating Groups I 差不多，只是数组首尾不再相接，判定条件从颜色交替变为字符相同。

Code

1
2
3
4
5
6
7
8

class Solution:
    def makeFancyString(self, s: str) -> str:
        n = len(s)
        parts = [s[:2]]
        for i in range(2, n):
            if s[i] != s[i-1] or s[i] != s[i-2]:
                parts.append(s[i])
        return ''.join(parts)

参考资料

• 本文引用

  • 3206. Alternating Groups I

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章