Lexicographically Smallest String After Applying Operations - Leetcode Solution

Problem Statement:

Given a string s and two integers a and b. You can choose any substring of s and replace at most a occurrences of the letter "a" and at most b occurrences of the letter "b".

Return the lexicographically smallest string you can obtain by doing this.

Example:

Input: s = "aabaa", a = 2, b = 2 Output: "aabaa" Explanation: You can transform the substring "aab" to "bba" if you replace "2" occurrences of "a" and "2" occurrences of "b", but it is not possible to obtain a lexicographically smaller string.

Approach:

In order to solve this problem, we can use the following approach:

1. Find the length of the given string.

2. We can apply operations repeatedly until there are no more possible substrings of length two to apply the operations to.

3. We can use a DFS to search for all possible substrings of length two and apply the operations on these substrings.

4. We can store each result we obtain through the operations and find the lexicographically smallest one from the list of results.

5. Once we have applied the operations to all possible substrings of length two, we can return the lexicographically smallest string from the list of results.

Code:

Here is the Python code that implements the approach we described above:

class Solution: def findLexSmallestString(self, s: str, a: int, b: int) -> str: res = [s] n = len(s) a = a % 10 if a > 10 else a for _ in range(b): s = s[-1] + s[:-1] if s in res: break else: res.append(s) for _ in range(a): tmp = list(s) for i in range(1, n, 2): tmp[i] = str((int(tmp[i]) + 1) % 10) s = "".join(tmp) if s in res: break else: res.append(s) return min(res)

1