Problem

A string is beautiful if:

  • It consists of the first k letters of the English lowercase alphabet.
  • It does not contain any substring of length 2 or more which is a palindrome.

You are given a beautiful string s of length n and a positive integer k.

Return the lexicographically smallest string of lengthn , which is larger thans and isbeautiful. If there is no such string, return an empty string.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

  • For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

Examples

Example 1

1
2
3
4

Input: s = "abcz", k = 26
Output: "abda"
Explanation: The string "abda" is beautiful and lexicographically larger than the string "abcz".
It can be proven that there is no string that is lexicographically larger than the string "abcz", beautiful, and lexicographically smaller than the string "abda".

Example 2

1
2
3

Input: s = "dc", k = 4
Output: ""
Explanation: It can be proven that there is no string that is lexicographically larger than the string "dc" and is beautiful.

Constraints

  • 1 <= n == s.length <= 10^5
  • 4 <= k <= 26
  • s is a beautiful string.

Solution

Method 1 – Greedy Backtracking

Intuition

To find the lexicographically smallest beautiful string greater than s, we try to increment the string from the end, ensuring that after each change, the string remains beautiful (no palindromic substrings of length 2 or 3). After incrementing, we greedily fill the rest with the smallest possible valid characters.

Approach

  1. Start from the end of the string and try to increment each character.
  2. For each position, try the next possible character (up to k-1).
  3. After incrementing, fill the rest of the string with the smallest valid characters (not forming palindromes with the previous 1 or 2 characters).
  4. If a valid string is found, return it. If not, return an empty string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    string smallestBeautifulString(string s, int k) {
        int n = s.size();
        for (int i = n-1; i >= 0; --i) {
            for (char c = s[i]+1; c < 'a'+k; ++c) {
                if ((i > 0 && c == s[i-1]) || (i > 1 && c == s[i-2])) continue;
                string t = s.substr(0, i) + c;
                for (int j = i+1; j < n; ++j) {
                    for (char d = 'a'; d < 'a'+k; ++d) {
                        if ((j > 0 && d == t[j-1]) || (j > 1 && d == t[j-2])) continue;
                        t += d;
                        break;
                    }
                }
                return t;
            }
        }
        return "";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func smallestBeautifulString(s string, k int) string {
    n := len(s)
    b := []byte(s)
    for i := n-1; i >= 0; i-- {
        for c := b[i]+1; c < byte('a'+k); c++ {
            if i > 0 && c == b[i-1] || i > 1 && c == b[i-2] { continue }
            t := append([]byte{}, b[:i]...)
            t = append(t, c)
            for j := i+1; j < n; j++ {
                for d := byte('a'); d < byte('a'+k); d++ {
                    if j > 0 && d == t[j-1] || j > 1 && d == t[j-2] { continue }
                    t = append(t, d)
                    break
                }
            }
            return string(t)
        }
    }
    return ""
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public String smallestBeautifulString(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = n-1; i >= 0; i--) {
            for (char c = (char)(arr[i]+1); c < (char)('a'+k); c++) {
                if ((i > 0 && c == arr[i-1]) || (i > 1 && c == arr[i-2])) continue;
                StringBuilder t = new StringBuilder(s.substring(0, i)).append(c);
                for (int j = i+1; j < n; j++) {
                    for (char d = 'a'; d < (char)('a'+k); d++) {
                        if ((j > 0 && d == t.charAt(j-1)) || (j > 1 && d == t.charAt(j-2))) continue;
                        t.append(d);
                        break;
                    }
                }
                return t.toString();
            }
        }
        return "";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun smallestBeautifulString(s: String, k: Int): String {
        val n = s.length
        val arr = s.toCharArray()
        for (i in n-1 downTo 0) {
            for (c in (arr[i]+1)..<('a'+k)) {
                if ((i > 0 && c == arr[i-1]) || (i > 1 && c == arr[i-2])) continue
                val t = StringBuilder(s.substring(0, i)).append(c)
                for (j in i+1 until n) {
                    for (d in 'a'..<'a'+k) {
                        if ((j > 0 && d == t[j-1]) || (j > 1 && d == t[j-2])) continue
                        t.append(d)
                        break
                    }
                }
                return t.toString()
            }
        }
        return ""
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        n = len(s)
        arr = list(s)
        for i in range(n-1, -1, -1):
            for c in range(ord(arr[i])+1, ord('a')+k):
                if (i > 0 and c == ord(arr[i-1])) or (i > 1 and c == ord(arr[i-2])):
                    continue
                t = arr[:i] + [chr(c)]
                for j in range(i+1, n):
                    for d in range(ord('a'), ord('a')+k):
                        if (j > 0 and d == ord(t[j-1])) or (j > 1 and d == ord(t[j-2])):
                            continue
                        t.append(chr(d))
                        break
                return ''.join(t)
        return ''
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn smallest_beautiful_string(s: String, k: i32) -> String {
        let n = s.len();
        let mut arr: Vec<u8> = s.bytes().collect();
        for i in (0..n).rev() {
            for c in arr[i]+1..b'a'+k as u8 {
                if (i > 0 && c == arr[i-1]) || (i > 1 && c == arr[i-2]) { continue; }
                let mut t = arr[..i].to_vec();
                t.push(c);
                for j in i+1..n {
                    for d in b'a'..b'a'+k as u8 {
                        if (j > 0 && d == t[j-1]) || (j > 1 && d == t[j-2]) { continue; }
                        t.push(d);
                        break;
                    }
                }
                return String::from_utf8(t).unwrap();
            }
        }
        String::new()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    smallestBeautifulString(s: string, k: number): string {
        const n = s.length;
        const arr = s.split('');
        for (let i = n-1; i >= 0; i--) {
            for (let c = arr[i].charCodeAt(0)+1; c < 'a'.charCodeAt(0)+k; c++) {
                if ((i > 0 && c === arr[i-1].charCodeAt(0)) || (i > 1 && c === arr[i-2].charCodeAt(0))) continue;
                const t = arr.slice(0, i).concat(String.fromCharCode(c));
                for (let j = i+1; j < n; j++) {
                    for (let d = 'a'.charCodeAt(0); d < 'a'.charCodeAt(0)+k; d++) {
                        if ((j > 0 && d === t[j-1].charCodeAt(0)) || (j > 1 && d === t[j-2].charCodeAt(0))) continue;
                        t.push(String.fromCharCode(d));
                        break;
                    }
                }
                return t.join('');
            }
        }
        return '';
    }
}

Complexity

  • ⏰ Time complexity: O(n*k^2), since for each position we may try up to k characters and for each, fill the rest with up to k choices.
  • 🧺 Space complexity: O(n), for the output string and temporary arrays.