Lexicographically Smallest Beautiful String - Solution & Explanation

Problem Overview: You are given a string s and an integer k representing the first k lowercase letters ('a' to 'a' + k - 1). A string is beautiful if no character equals the previous one or the one two positions before it. The task is to find the lexicographically smallest beautiful string strictly greater than s.

Approach 1: Backtrack and Increment (O(n * k) time, O(1) space)

This method treats the string like a base-k number and increments it from right to left. Start from the last position and try increasing the current character. After each increment, check whether it violates the beauty rule (s[i] != s[i-1] and s[i] != s[i-2]). If the character is valid, rebuild the suffix greedily with the smallest valid characters that keep the string beautiful. If no valid increment exists at a position, move left and continue backtracking.

The key insight: once you increase a character at position i, the prefix becomes fixed. The suffix can then be rebuilt with the smallest valid characters to maintain lexicographic minimality. This approach simulates controlled backtracking while preserving the lexicographically smallest valid continuation. It relies heavily on simple character checks and sequential iteration, making it efficient for constraints typically seen in string problems.

Approach 2: Greedy Character Replacement (O(n * k) time, O(1) space)

The greedy strategy scans the string from right to left and attempts to replace each character with the next valid option. For index i, iterate characters from s[i] + 1 to 'a' + k - 1. Choose the first character that doesn't match the previous two characters. Once a valid replacement is found, rebuild the remaining suffix by picking the smallest valid character at each step.

This works because lexicographic order is determined by the earliest differing character. Increasing the rightmost possible index ensures the smallest overall increase. The suffix reconstruction step uses a greedy rule: always choose the smallest character that doesn't conflict with the previous two positions. The approach combines simple iteration with constraints typical in greedy algorithms and local validation rules from string manipulation.

Recommended for interviews: The greedy right-to-left increment approach is what most interviewers expect. It demonstrates understanding of lexicographic ordering, constraint validation, and suffix reconstruction. Mentioning the backtracking interpretation shows deeper reasoning, but implementing the greedy increment + rebuild pattern proves strong problem‑solving skills.