# Lexicographically Smallest Beautiful String
**Difficulty:** HARD
[External](https://leetcode.com/problems/lexicographically-smallest-beautiful-string)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-smallest-beautiful-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## 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 length_ `n`_, which is larger than_ `s` _and is **beautiful**_. 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`.

**Example 1:**

**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:**

**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 <= 105`
* `4 <= k <= 26`
* `s` is a beautiful string.

# Approaches
## Brute-Force by Generating and Checking
This approach involves generating every possible string that is lexicographically larger than the input string `s`, one by one. For each generated string, we check if it meets the criteria of a "beautiful" string. The first one that satisfies the conditions is our answer.
**Time:** O(M * n), where `M` is the number of strings between `s` and the result. In the worst case, `M` can be very large (e.g., on the order of `k^n`), making this approach infeasible for the given constraints. · **Space:** O(n) to store the character array for the current string.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient. It will time out for the given constraints (`n` up to 10^5) because the number of strings to check can be astronomically large.; Performs a lot of redundant work by re-validating the entire string from scratch for every single increment.
### Explanation
The core idea is to treat the strings as numbers in base `k`, where 'a' corresponds to 0, 'b' to 1, and so on. We start with the string `s` and repeatedly find the "next" string in lexicographical order. The process of finding the next string is analogous to adding one to a number. We start from the rightmost character and increment it. If the character exceeds the allowed limit (`'a' + k - 1`), we reset it to 'a' and "carry over" the increment to the character on its left.

After generating a new string, we must validate if it's "beautiful". A string is beautiful if it only contains the first `k` letters and has no palindromic substrings of length 2 or 3. This means for any index `i`, `s[i] != s[i-1]` and `s[i] != s[i-2]`. This validation check takes linear time, `O(n)`.

We continue this process of generating and validating until we find a beautiful string or exhaust all possible strings of length `n` that are larger than `s`.

```java
class Solution {
    public String smallestBeautifulString(String s, int k) {
        char[] chars = s.toCharArray();
        int n = s.length();

        while (true) {
            // Increment the string like a base-k number
            int i = n - 1;
            while (i >= 0) {
                chars[i]++;
                if (chars[i] < 'a' + k) {
                    break;
                }
                chars[i] = 'a';
                i--;
            }

            // If i < 0, we have overflowed, no more strings
            if (i < 0) {
                return "";
            }

            // Check if the new string is beautiful
            if (isBeautiful(chars)) {
                // We need to construct the rest of the string to be minimal
                // This simple brute force doesn't do that, it just checks the next permutation.
                // A better brute force would fill the rest with 'a's and check.
                // But the core issue of iterating one by one remains.
                // For the sake of demonstrating the concept, let's assume a full beautiful check.
                return new String(chars);
            }
        }
    }

    private boolean isBeautiful(char[] chars) {
        for (int i = 0; i < chars.length; i++) {
            if (i > 0 && chars[i] == chars[i-1]) {
                return false;
            }
            if (i > 1 && chars[i] == chars[i-2]) {
                return false;
            }
        }
        return true;
    }
}
```
*Note: The provided code is a conceptual illustration. A direct implementation of generating every single next string and checking it would be too slow. The main flaw is the sheer number of candidates to check.*
### Algorithm
- Start with the input string `s`.
- Enter a loop that generates the next lexicographically larger string, let's call it `current_s`.
- To generate `current_s` from `s`:
    - Convert `s` to a character array `chars`.
    - Iterate from `i = n-1` down to `0`.
    - Increment `chars[i]`.
    - If `chars[i]` is less than `'a' + k`, we have found the next string. Break the inner loop.
    - If `chars[i]` becomes equal to `'a' + k`, set `chars[i] = 'a'` and continue to the next position to the left (this is a carry-over operation).
    - If the inner loop finishes (i.e., we carried over from index 0), it means we have exhausted all strings of length `n`. There is no solution.
- Check if `current_s` is beautiful:
    - Iterate from `i = 0` to `n-1`.
    - Check if `chars[i] == chars[i-1]` (for `i > 0`).
    - Check if `chars[i] == chars[i-2]` (for `i > 1`).
    - If any check fails, the string is not beautiful. Go back to the beginning of the main loop to generate the next string.
- If `current_s` is beautiful, convert `chars` to a string and return it.
- If the generation process exhausts all possibilities without finding a solution, return an empty string.

## Greedy Modification from Right to Left
This is an efficient, greedy approach. To find the lexicographically smallest string larger than `s`, we should make the smallest possible change, and as far to the right as possible. We iterate from the right end of the string, trying to increment the character at each position. Once we successfully increment a character while keeping it "beautiful" with respect to its predecessors, we fill the rest of the string to its right with the smallest possible beautiful characters.
**Time:** O(n * k). The outer loop runs at most `n` times. For each position, we might try up to `k` characters. Once a pivot is found at index `p`, filling the `n-p-1` suffix takes `O(n-p)` time, as each character fill is constant time (due to `k>=4`). The total time is dominated by finding the pivot, which in the worst case (pivot at index 0) is `O(n*k)`. Since `k` is a small constant (<= 26), this is effectively a linear time complexity, `O(n)`. · **Space:** O(n) to store the character array. If modification of the input string is allowed, space can be considered O(1) (excluding the space for the output string).
**Pros:** Highly efficient and guaranteed to find the optimal solution.; The time complexity is effectively linear with respect to the length of the string, making it suitable for large inputs.; Correctly leverages the problem constraints (`k >= 4`) to ensure an efficient solution.
**Cons:** The logic is slightly more complex to implement compared to a naive brute-force approach.
### Explanation
The algorithm starts by scanning the string `s` from right to left (from index `n-1` down to `0`). At each position `i`, we try to find a character `c` that is greater than `s[i]` but still within the first `k` letters.

For each potential character `c`, we must check if it's valid. A character is valid if it doesn't form a palindrome with the characters at `i-1` and `i-2`. That is, `c` must not be equal to `s[i-1]` or `s[i-2]`.

If we find such a valid character `c`, we have found our "pivot". We update the character at index `i` to `c`. Then, we must fill all the subsequent positions (`j > i`) to make the resulting string as small as possible lexicographically. For each position `j` from `i+1` to `n-1`, we greedily pick the smallest possible character ('a', 'b', 'c', ...) that is valid (i.e., doesn't equal the characters at `j-1` and `j-2`). Since the problem guarantees `k >= 4`, a valid character among 'a', 'b', 'c' is always guaranteed to exist.

Once we have modified the character at `i` and filled the rest of the string, we have found our answer. If we iterate through all positions and cannot find any character to increment, no such string exists.

```java
class Solution {
    public String smallestBeautifulString(String s, int k) {
        char[] chars = s.toCharArray();
        int n = chars.length;

        // Iterate from right to left
        for (int i = n - 1; i >= 0; i--) {
            // Try to increment the character at position i
            for (char c = (char)(chars[i] + 1); c < 'a' + k; c++) {
                // Check if the new character c is valid (no length-2 or -3 palindrome)
                if ((i > 0 && c == chars[i - 1]) || (i > 1 && c == chars[i - 2])) {
                    continue; // Invalid, try next character
                }

                // Found a valid character, this is our pivot
                chars[i] = c;

                // Fill the rest of the string from i + 1 to n - 1
                for (int j = i + 1; j < n; j++) {
                    // Find the smallest valid character for position j
                    for (char fillChar = 'a'; fillChar < 'a' + k; fillChar++) {
                        if ((j > 0 && fillChar == chars[j - 1]) || (j > 1 && fillChar == chars[j - 2])) {
                            continue;
                        }
                        chars[j] = fillChar;
                        break; // Found the smallest, move to next position
                    }
                }
                return new String(chars);
            }
        }

        // If we went through the whole loop, no such string exists
        return "";
    }
}
```
### Algorithm
- Convert the input string `s` to a character array `chars` for efficient modification.
- Iterate `i` from the end of the string (`n-1`) down to the beginning (`0`).
- For the character `chars[i]`, try to find a valid replacement `c`. Start checking from `c = chars[i] + 1`.
- Loop `c` from `chars[i] + 1` up to `'a' + k - 1`.
- Check if `c` is valid at position `i`. A character is valid if it's not equal to the two preceding characters:
    - `c` must not be equal to `chars[i-1]` (if `i > 0`).
    - `c` must not be equal to `chars[i-2]` (if `i > 1`).
- If a valid `c` is found:
    - This position `i` is our "pivot". Update `chars[i] = c`.
    - Now, fill the suffix of the string from `j = i + 1` to `n-1`.
    - For each position `j`, greedily find the smallest character `fill_c` (starting from 'a') that is valid (i.e., not equal to `chars[j-1]` or `chars[j-2]`).
    - Update `chars[j] = fill_c`.
    - After the suffix is filled, convert `chars` back to a string and return it. This is the final answer.
- If the outer loop (from `n-1` to `0`) completes without finding a valid replacement for any character, it means no such string exists. Return an empty string.

# Solutions
### Java

```java
class Solution {
public
  String smallestBeautifulString(String s, int k) {
    int n = s.length();
    char[] cs = s.toCharArray();
    for (int i = n - 1; i >= 0; --i) {
      int p = cs[i] - 'a' + 1;
      for (int j = p; j < k; ++j) {
        char c = (char)('a' + j);
        if ((i > 0 && cs[i - 1] == c) || (i > 1 && cs[i - 2] == c)) {
          continue;
        }
        cs[i] = c;
        for (int l = i + 1; l < n; ++l) {
          for (int m = 0; m < k; ++m) {
            c = (char)('a' + m);
            if ((l > 0 && cs[l - 1] == c) || (l > 1 && cs[l - 2] == c)) {
              continue;
            }
            cs[l] = c;
            break;
          }
        }
        return String.valueOf(cs);
      }
    }
    return "";
  }
}

```

### CPP

```cpp
class Solution {
public:
  string smallestBeautifulString(string s, int k) {
    int n = s.size();
    for (int i = n - 1; i >= 0; --i) {
      int p = s[i] - 'a' + 1;
      for (int j = p; j < k; ++j) {
        char c = (char)('a' + j);
        if ((i > 0 && s[i - 1] == c) || (i > 1 && s[i - 2] == c)) {
          continue;
        }
        s[i] = c;
        for (int l = i + 1; l < n; ++l) {
          for (int m = 0; m < k; ++m) {
            c = (char)('a' + m);
            if ((l > 0 && s[l - 1] == c) || (l > 1 && s[l - 2] == c)) {
              continue;
            }
            s[l] = c;
            break;
          }
        }
        return s;
      }
    }
    return "";
  }
};

```

### Python

```python
class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str: n = len(s) cs = list(s) for i in range(n - 1, - 1, - 1): p = ord(cs[i]) - ord('a') + 1 for j in range(p, k): c = chr(ord('a') + j) if (i > 0 and cs[i - 1] == c) or (i > 1 and cs[i - 2] == c): continue cs[i] = c for l in range(i + 1, n): for m in range(k): c = chr(ord('a') + m) if (l > 0 and cs[l - 1] == c) or (l > 1 and cs[l - 2] == c): continue cs[l] = c break return '' . join(cs) return ''

```