Lexicographically Smallest Beautiful String

Hard
1263.

Lexicographically Smallest Beautiful String

Lexicographically Smallest Beautiful String is a hard coding problem on strings and greedy, asked in Amazon and Google interviews.

A string is beautiful when:

  • it uses only the first k lowercase letters of the alphabet, and
  • it contains no palindromic substring of length 2 or more.

You are given a beautiful string s of length n and the integer k. Return the lexicographically smallest beautiful string of length n that is strictly larger than s, or an empty string if there is none.

Example 1

Input
s = "kaib", k = 12
Output
"kaic"
Explanation
Raising the last letter to `c` keeps every window palindrome-free.

Example 2

Input
s = "dcb", k = 4
Output
""
Explanation
With only `a`–`d`, no position can be raised without creating a palindrome.

Example 3

Input
s = "abcd", k = 4
Output
"abda"
Explanation
The last letter is already `d`; raise the third to `d` and fill the rest with the smallest safe letter.

Constraints

  • 1 <= n == s.length <= 10^5
  • 4 <= k <= 26
  • s is a beautiful string
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var smallestBeautifulString = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Lexicographically Smallest Beautiful String — Solution

Lexicographically Smallest Beautiful String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Lexicographically Smallest Beautiful String is a hard coding problem on strings and greedy, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Strings, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string is beautiful when:

  • it uses only the first k lowercase letters of the alphabet, and
  • it contains no palindromic substring of length 2 or more.

You are given a beautiful string s of length n and the integer k. Return the lexicographically smallest beautiful string of length n that is strictly larger than s, or an empty string if there is none.

Example 1

Input: s = "kaib", k = 12
Output: "kaic"
Explanation: Raising the last letter to `c` keeps every window palindrome-free.

Example 2

Input: s = "dcb", k = 4
Output: ""
Explanation: With only `a`–`d`, no position can be raised without creating a palindrome.

Example 3

Input: s = "abcd", k = 4
Output: "abda"
Explanation: The last letter is already `d`; raise the third to `d` and fill the rest with the smallest safe letter.

Constraints

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

Hints for Lexicographically Smallest Beautiful String

  1. Hint 1

    A string has no palindromic substring of length >= 2 exactly when no character equals either of the two characters before it.

  2. Hint 2

    To get the next string, keep the longest possible prefix of s: try to raise the last position first, then the one before it, and so on.

  3. Hint 3

    At position i, try letters above s[i] (below k) that differ from the two previous letters. Once one works, fill every later position with the smallest letter that differs from its two predecessors — with k >= 4 one of a, b, c always works.

How to solve Lexicographically Smallest Beautiful String

Beauty is a local rule (each letter differs from the previous two), so the next beautiful string keeps the longest prefix of s it can, bumps one position minimally, and fills the tail greedily with the smallest legal letters.

Approach

  1. Convert s to letter indices a[0..n-1].
  2. For i from n - 1 down to 0: look for the smallest c with a[i] < c < k, c != a[i-1] and c != a[i-2] (where those exist).
  3. If found, set a[i] = c, then for each j > i set a[j] to the smallest letter different from a[j-1] and a[j-2], and return the result.
  4. If no position can be raised, return the empty string.

Why it works

A palindrome of length >= 2 contains a palindrome of length 2 or 3 at its centre, so forbidding x[j] == x[j-1] and x[j] == x[j-2] is equivalent to beauty. The answer must share the longest possible prefix with s and then have a larger letter at the first difference, and that letter should be as small as possible; after it, any suffix is allowed, so the smallest choice letter by letter is optimal — and it always exists because at most two letters are forbidden while k >= 4.

Complexity

  • Time — O(n · k)
  • Space — O(n)

Pitfalls

  • Checking only adjacent letters misses length-3 palindromes like aba.
  • The new letter must stay below k, not below z.
  • When filling the tail, check against the new letters already placed, not the original s.

Reference solution

Python

def smallestBeautifulString(s: str, k: int) -> str:
    a = [ord(c) - 97 for c in s]
    n = len(a)
    for i in range(n - 1, -1, -1):
        c = a[i] + 1
        while c < k and ((i >= 1 and a[i - 1] == c) or (i >= 2 and a[i - 2] == c)):
            c += 1
        if c < k:
            a[i] = c
            for j in range(i + 1, n):
                x = 0
                while (j >= 1 and a[j - 1] == x) or (j >= 2 and a[j - 2] == x):
                    x += 1
                a[j] = x
            return "".join(chr(97 + x) for x in a)
    return ""

Java

public static String smallestBeautifulString(String s, int k) {
    int n = s.length();
    char[] a = s.toCharArray();
    for (int i = n - 1; i >= 0; i--) {
        int c = a[i] - 'a' + 1;
        while (c < k && ((i >= 1 && a[i - 1] - 'a' == c) || (i >= 2 && a[i - 2] - 'a' == c))) c++;
        if (c < k) {
            a[i] = (char) ('a' + c);
            for (int j = i + 1; j < n; j++) {
                int x = 0;
                while ((j >= 1 && a[j - 1] - 'a' == x) || (j >= 2 && a[j - 2] - 'a' == x)) x++;
                a[j] = (char) ('a' + x);
            }
            return new String(a);
        }
    }
    return "";
}

C++

string smallestBeautifulString(string s, int k) {
    int n = s.size();
    for (int i = n - 1; i >= 0; i--) {
        int c = s[i] - 'a' + 1;
        while (c < k && ((i >= 1 && s[i - 1] - 'a' == c) || (i >= 2 && s[i - 2] - 'a' == c))) c++;
        if (c < k) {
            s[i] = (char)('a' + c);
            for (int j = i + 1; j < n; j++) {
                int x = 0;
                while ((j >= 1 && s[j - 1] - 'a' == x) || (j >= 2 && s[j - 2] - 'a' == x)) x++;
                s[j] = (char)('a' + x);
            }
            return s;
        }
    }
    return "";
}

JavaScript

var smallestBeautifulString = function(s, k) {
    var n = s.length;
    var a = [];
    for (var q = 0; q < n; q++) a.push(s.charCodeAt(q) - 97);
    for (var i = n - 1; i >= 0; i--) {
        var c = a[i] + 1;
        while (c < k && ((i >= 1 && a[i - 1] === c) || (i >= 2 && a[i - 2] === c))) c++;
        if (c < k) {
            a[i] = c;
            for (var j = i + 1; j < n; j++) {
                var x = 0;
                while ((j >= 1 && a[j - 1] === x) || (j >= 2 && a[j - 2] === x)) x++;
                a[j] = x;
            }
            var res = "";
            for (var p = 0; p < n; p++) res += String.fromCharCode(97 + a[p]);
            return res;
        }
    }
    return "";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms