# Lexicographically Smallest String After Applying Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-smallest-string-after-applying-operations
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** String
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
You are given a string `s` of **even length** consisting of digits from `0` to `9`, and two integers `a` and `b`.

You can apply either of the following two operations any number of times and in any order on `s`:

* Add `a` to all odd indices of `s` **(0-indexed)**. Digits post `9` are cycled back to `0`. For example, if `s = "3456"` and `a = 5`, `s` becomes `"3951"`.
* Rotate `s` to the right by `b` positions. For example, if `s = "3456"` and `b = 1`, `s` becomes `"6345"`.

Return _the **lexicographically smallest** string you can obtain by applying the above operations any number of times on_ `s`.

A string `a` is lexicographically smaller than a string `b` (of the same length) if in the first position where `a` and `b` differ, string `a` has a letter that appears earlier in the alphabet than the corresponding letter in `b`. For example, `"0158"` is lexicographically smaller than `"0190"` because the first position they differ is at the third letter, and `'5'` comes before `'9'`.

**Example 1:**

**Input:** s = "5525", a = 9, b = 2
**Output:** "2050"
**Explanation:** We can apply the following operations:
Start:  "5525"
Rotate: "2555"
Add:    "2454"
Add:    "2353"
Rotate: "5323"
Add:    "5222"
Add:    "5121"
Rotate: "2151"
Add:    "2050"​​​​​
There is no way to obtain a string that is lexicographically smaller than "2050".

**Example 2:**

**Input:** s = "74", a = 5, b = 1
**Output:** "24"
**Explanation:** We can apply the following operations:
Start:  "74"
Rotate: "47"
​​​​​​​Add:    "42"
​​​​​​​Rotate: "24"​​​​​​​​​​​​
There is no way to obtain a string that is lexicographically smaller than "24".

**Example 3:**

**Input:** s = "0011", a = 4, b = 2
**Output:** "0011"
**Explanation:** There are no sequence of operations that will give us a lexicographically smaller string than "0011".

**Constraints:**

* `2 <= s.length <= 100`
* `s.length` is even.
* `s` consists of digits from `0` to `9` only.
* `1 <= a <= 9`
* `1 <= b <= s.length - 1`

# Approaches
## Recursive Depth-First Search (DFS)
This approach uses a recursive Depth-First Search (DFS) to explore all possible strings that can be generated. Starting with the initial string, it recursively explores the outcomes of applying the 'add' and 'rotate' operations. A `Set` is used to keep track of visited strings to prevent infinite loops and avoid re-processing the same string, making the exploration efficient.
**Time:** O(S * n), where `S` is the number of reachable states and `n` is the string length. Each state is processed once, and processing involves string operations that take O(n) time. The number of states `S` is bounded by `(n/gcd(n,b)) * (10/gcd(a,10))`, which is at most `10n`. Thus, the time complexity is O(n^2). · **Space:** O(S * n), where `S` is the number of reachable states and `n` is the string length. The space is used for the `visited` set and the recursion stack. Since `S` is at most `10n`, the complexity is O(n^2).
**Pros:** The logic is straightforward to implement for those familiar with recursion and graph traversal.; It is guaranteed to find the correct lexicographically smallest string by exploring all reachable states.
**Cons:** If the state space graph is deep, this approach can lead to a `StackOverflowError` due to deep recursion. The maximum recursion depth could be up to the total number of states.; While having the same theoretical time complexity as BFS, the overhead of function calls in recursion can sometimes be slightly higher than the iterative approach of BFS.
### Explanation
The problem of finding the lexicographically smallest string can be modeled as finding a specific node in a state-space graph. Each unique string is a node, and the operations are edges. A Depth-First Search is a natural way to traverse this graph.

We start a recursive traversal from the initial string `s`. A global variable, `minString`, is maintained to store the lexicographically smallest string found so far. To make the search efficient and to prevent getting stuck in cycles (e.g., rotating `n/b` times by `b` gets back to the original string), we use a `HashSet` to store all the strings (states) we have already visited. 

In each step of the recursion, we take the current string, check if it's smaller than our current `minString`, and update if necessary. Then, we generate two new strings by applying the 'add' and 'rotate' operations. For each new string, we make a recursive call only if it has not been visited before. This ensures that every reachable state is processed exactly once.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    String minString;
    Set<String> visited;
    int a;
    int b;

    public String findLexSmallestString(String s, int a, int b) {
        this.minString = s;
        this.visited = new HashSet<>();
        this.a = a;
        this.b = b;
        dfs(s);
        return minString;
    }

    private void dfs(String s) {
        if (visited.contains(s)) {
            return;
        }
        visited.add(s);

        if (s.compareTo(minString) < 0) {
            minString = s;
        }

        // Apply add operation
        dfs(applyAdd(s));

        // Apply rotate operation
        dfs(applyRotate(s));
    }

    private String applyAdd(String s) {
        char[] chars = s.toCharArray();
        for (int i = 1; i < chars.length; i += 2) {
            int digit = chars[i] - '0';
            digit = (digit + a) % 10;
            chars[i] = (char) (digit + '0');
        }
        return new String(chars);
    }

    private String applyRotate(String s) {
        int n = s.length();
        return s.substring(n - b) + s.substring(0, n - b);
    }
}
```
### Algorithm
- Initialize a global variable `minString` with the input string `s`.
- Create a `Set<String>` called `visited` to keep track of processed strings to avoid cycles and redundant computations.
- Define a recursive function `dfs(String current)`.
- Inside `dfs(current)`:
  - If `current` is already in `visited`, return immediately.
  - Add `current` to the `visited` set.
  - Compare `current` with `minString`. If `current` is lexicographically smaller, update `minString`.
  - Apply the 'add' operation to `current` to get `addString`. Make a recursive call: `dfs(addString)`.
  - Apply the 'rotate' operation to `current` to get `rotateString`. Make a recursive call: `dfs(rotateString)`.
- Start the process by calling `dfs(s)` from the main function.
- After the recursion completes, `minString` will hold the result.

## Breadth-First Search (BFS) on State Space Graph
This approach models the problem as finding a node in a state-space graph. Each unique string that can be generated is a node, and the two operations ('add' and 'rotate') represent directed edges. We start from the initial string `s` and explore all reachable strings using an iterative Breadth-First Search (BFS). By keeping track of visited strings in a `Set`, we ensure each state is processed only once, making the algorithm efficient.
**Time:** O(S * n), where `S` is the number of reachable states and `n` is the string length. Each of the `S` states is processed once. Processing involves string creation, comparison, and hashing, each taking O(n) time. Since `S` is at most `10n`, the total time complexity is O(n^2). · **Space:** O(S * n), where `S` is the number of reachable states and `n` is the string length. Space is dominated by the `visited` set and the `queue`. Since `S` is at most `10n`, the complexity is O(n^2).
**Pros:** Guaranteed to find the lexicographically smallest string by exhaustively and efficiently exploring all possibilities.; Avoids deep recursion and the risk of stack overflow, making it more robust than a recursive DFS for graphs with long paths.; The time and space complexity are very good for the given constraints due to the small size of the state space.
**Cons:** Requires extra space for the queue and the visited set, which can be significant if the number of states is large, although it's manageable for this problem's constraints.
### Explanation
A Breadth-First Search (BFS) is an ideal algorithm for systematically exploring all reachable states from a starting point, which is exactly what this problem requires. We can think of the initial string `s` as the root of a graph, and the 'add' and 'rotate' operations as ways to discover new, connected nodes (strings).

We use a queue to manage the order of strings to visit, ensuring that we explore the graph level by level. A `HashSet` is used to keep track of visited strings to avoid redundant computations and infinite loops. 

The process begins by adding the initial string `s` to both the queue and the `visited` set. We also initialize our answer, `minString`, to `s`. Then, we repeatedly dequeue a string, apply the two operations to generate potential new strings, and if a generated string hasn't been visited, we add it to our `visited` set and the queue. Every string taken from the queue is compared with `minString` to find the lexicographically smallest one.

The efficiency of this approach hinges on the total number of unique strings we can generate. The number of distinct rotations is at most `n`. For any given string, the 'add' operation can produce at most 10 unique variants (as adding `a` ten times cycles back). The total number of reachable states is bounded by `(n/gcd(n,b)) * (10/gcd(a,10))`, which is at most `10n`. Given `n <= 100`, the state space is small enough for this approach to be very fast.

```java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public String findLexSmallestString(String s, int a, int b) {
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        String minString = s;

        queue.offer(s);
        visited.add(s);

        while (!queue.isEmpty()) {
            String current = queue.poll();

            if (current.compareTo(minString) < 0) {
                minString = current;
            }

            // Apply add operation
            char[] addChars = current.toCharArray();
            for (int i = 1; i < addChars.length; i += 2) {
                int digit = addChars[i] - '0';
                digit = (digit + a) % 10;
                addChars[i] = (char) (digit + '0');
            }
            String added = new String(addChars);
            if (visited.add(added)) {
                queue.offer(added);
            }

            // Apply rotate operation
            int n = current.length();
            String rotated = current.substring(n - b) + current.substring(0, n - b);
            if (visited.add(rotated)) {
                queue.offer(rotated);
            }
        }
        return minString;
    }
}
```
### Algorithm
- Initialize a `Queue<String>` and add the initial string `s` to it.
- Initialize a `Set<String>` called `visited` and add `s` to it. This set will store all strings that have been enqueued to prevent processing them again.
- Initialize a string variable `minString` to `s`.
- Loop while the queue is not empty:
  - Dequeue a string, let's call it `current`.
  - Compare `current` with `minString`. If `current` is lexicographically smaller, update `minString`.
  - Apply the 'add' operation on `current` to get `addString`. If `addString` has not been visited, add it to the `visited` set and enqueue it.
  - Apply the 'rotate' operation on `current` to get `rotateString`. If `rotateString` has not been visited, add it to the `visited` set and enqueue it.
- After the loop terminates (when all reachable states have been visited), `minString` holds the result.

# Solutions
### Java

```java
class Solution {
public
  String findLexSmallestString(String s, int a, int b) {
    Deque<String> q = new ArrayDeque<>();
    q.offer(s);
    Set<String> vis = new HashSet<>();
    vis.add(s);
    String ans = s;
    int n = s.length();
    while (!q.isEmpty()) {
      s = q.poll();
      if (ans.compareTo(s) > 0) {
        ans = s;
      }
      char[] cs = s.toCharArray();
      for (int i = 1; i < n; i += 2) {
        cs[i] = (char)(((cs[i] - '0' + a) % 10) + '0');
      }
      String t1 = String.valueOf(cs);
      String t2 = s.substring(n - b) + s.substring(0, n - b);
      for (String t : List.of(t1, t2)) {
        if (vis.add(t)) {
          q.offer(t);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string findLexSmallestString(string s, int a, int b) {
    queue<string> q{{s}};
    unordered_set<string> vis{{s}};
    string ans = s;
    int n = s.size();
    while (!q.empty()) {
      s = q.front();
      q.pop();
      ans = min(ans, s);
      string t1 = s;
      for (int i = 1; i < n; i += 2) {
        t1[i] = (t1[i] - '0' + a) % 10 + '0';
      }
      string t2 = s.substr(n - b) + s.substr(0, n - b);
      for (auto &t : {t1, t2}) {
        if (!vis.count(t)) {
          vis.insert(t);
          q.emplace(t);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str: q = deque([s]) vis = {s} ans = s while q: s = q . popleft() if ans > s: ans = s t1 = '' . join([str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)]) t2 = s[- b:] + s[: - b] for t in (t1, t2): if t not in vis: vis . add(t) q . append(t) return ans

```