Skip to content

2663. Lexicographically Smallest Beautiful String 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  string smallestBeautifulString(string s, int k) {
    for (int i = s.length() - 1; i >= 0; --i) {
      do {
        ++s[i];
      } while (containsPalindrome(s, i));
      if (s[i] < 'a' + k)
        // If s[i] is among the first k letters, then change the letters after
        // s[i] to the smallest ones that don't form any palindrome substring.
        return changeSuffix(s, i + 1);
    }

    return "";
  }

 private:
  // Returns true if s[0..i] contains any palindrome.
  bool containsPalindrome(const string& s, int i) {
    return (i > 0 && s[i] == s[i - 1]) || (i > 1 && s[i] == s[i - 2]);
  }

  // Returns a string, where replacing s[i..n) with the smallest possible
  // letters don't form any palindrome substring.
  string changeSuffix(string& s, int i) {
    for (int j = i; j < s.length(); ++j)
      for (s[j] = 'a'; containsPalindrome(s, j); ++s[j])
        ;
    return s;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
  public String smallestBeautifulString(String s, int k) {
    StringBuilder sb = new StringBuilder(s);

    for (int i = s.length() - 1; i >= 0; --i) {
      do {
        sb.setCharAt(i, (char) (sb.charAt(i) + 1));
      } while (containsPalindrome(sb, i));
      if (sb.charAt(i) < 'a' + k)
        // If sb[i] is among the first k letters, then change the letters after
        // sb[i] to the smallest ones that don't form any palindrome substring.
        return changeSuffix(sb, i + 1);
    }

    return "";
  }

  // Returns true if sb[0..i] contains any palindrome.
  private boolean containsPalindrome(StringBuilder sb, int i) {
    return (i > 0 && sb.charAt(i) == sb.charAt(i - 1)) ||
        (i > 1 && sb.charAt(i) == sb.charAt(i - 2));
  }

  // Returns a string, where replacing sb[i..n) with the smallest possible
  // letters don't form any palindrome substring.
  private String changeSuffix(StringBuilder sb, int i) {
    for (int j = i; j < sb.length(); ++j)
      for (sb.setCharAt(j, 'a'); containsPalindrome(sb, j);
           sb.setCharAt(j, (char) (sb.charAt(j) + 1)))
        ;
    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
  def smallestBeautifulString(self, s: str, k: int) -> str:
    chars = list(s)

    for i in reversed(range(len(chars))):
      chars[i] = chr(ord(chars[i]) + 1)
      while self._containsPalindrome(chars, i):
        chars[i] = chr(ord(chars[i]) + 1)
      if chars[i] < chr(ord('a') + k):
        # If s[i] is among the first k letters, then change the letters after
        # s[i] to the smallest ones that don't form any palindrome substring.
        return self._changeSuffix(chars, i + 1)

    return ''

  def _containsPalindrome(self, chars: List[str], i: int) -> bool:
    """Returns True if chars[0..i] contains palindrome."""
    return (i > 0 and chars[i] == chars[i - 1]) or \
        (i > 1 and chars[i] == chars[i - 2])

  def _changeSuffix(self, chars: List[str], i: int) -> str:
    """
    Returns a string, where replacing sb[i..n) with the smallest possible
    letters don't form any palindrome substring.
    """
    for j in range(i, len(chars)):
      chars[j] = 'a'
      while self._containsPalindrome(chars, j):
        chars[j] = chr(ord(chars[j]) + 1)
    return ''.join(chars)