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 thelexicographically 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'.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

1
2
3
4
5
6
7
8

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

1
2
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

Solution

Method 1 – BFS/DFS Enumeration

Intuition

Since both operations (add and rotate) can be applied any number of times, and the string is of even length, we can use BFS or DFS to explore all reachable strings. We keep track of visited states to avoid cycles and always update the answer with the lexicographically smallest string found.

Approach

  1. Use a set to keep track of visited strings.
  2. Use a queue (BFS) or stack (DFS) to explore all possible strings.
  3. For each string, generate the next states by:
    • Adding a to all odd indices (modulo 10).
    • Rotating the string to the right by b positions.
  4. If a new string is found, add it to the queue/stack and visited set.
  5. Track the lexicographically smallest string seen.
  6. Return the smallest string after the search.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        unordered_set<string> vis;
        queue<string> q;
        string ans = s;
        q.push(s);
        vis.insert(s);
        while (!q.empty()) {
            string cur = q.front(); q.pop();
            if (cur < ans) ans = cur;
            // Add a to odd indices
            string t = cur;
            for (int i = 1; i < t.size(); i += 2) t[i] = (t[i]-'0'+a)%10 + '0';
            if (!vis.count(t)) { vis.insert(t); q.push(t); }
            // Rotate by b
            t = cur.substr(cur.size()-b) + cur.substr(0, cur.size()-b);
            if (!vis.count(t)) { vis.insert(t); q.push(t); }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func findLexSmallestString(s string, a, b int) string {
    vis := map[string]bool{}
    q := []string{s}
    ans := s
    vis[s] = true
    for len(q) > 0 {
        cur := q[0]; q = q[1:]
        if cur < ans { ans = cur }
        // Add a to odd indices
        t := []byte(cur)
        for i := 1; i < len(t); i += 2 {
            t[i] = byte((int(t[i]-'0')+a)%10 + '0')
        }
        tstr := string(t)
        if !vis[tstr] { vis[tstr] = true; q = append(q, tstr) }
        // Rotate by b
        tstr = cur[len(cur)-b:] + cur[:len(cur)-b]
        if !vis[tstr] { vis[tstr] = true; q = append(q, tstr) }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public String findLexSmallestString(String s, int a, int b) {
        Set<String> vis = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        String ans = s;
        q.add(s);
        vis.add(s);
        while (!q.isEmpty()) {
            String cur = q.poll();
            if (cur.compareTo(ans) < 0) ans = cur;
            // Add a to odd indices
            char[] t = cur.toCharArray();
            for (int i = 1; i < t.length; i += 2) t[i] = (char)((t[i]-'0'+a)%10 + '0');
            String tstr = new String(t);
            if (vis.add(tstr)) q.add(tstr);
            // Rotate by b
            tstr = cur.substring(cur.length()-b) + cur.substring(0, cur.length()-b);
            if (vis.add(tstr)) q.add(tstr);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun findLexSmallestString(s: String, a: Int, b: Int): String {
        val vis = mutableSetOf<String>()
        val q = ArrayDeque<String>()
        var ans = s
        q.add(s)
        vis.add(s)
        while (q.isNotEmpty()) {
            val cur = q.removeFirst()
            if (cur < ans) ans = cur
            // Add a to odd indices
            val t = cur.toCharArray()
            for (i in 1 until t.size step 2) t[i] = ((t[i]-'0'+a)%10 + '0'.toInt()).toChar()
            val tstr = String(t)
            if (vis.add(tstr)) q.add(tstr)
            // Rotate by b
            val rot = cur.takeLast(b) + cur.dropLast(b)
            if (vis.add(rot)) q.add(rot)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        from collections import deque
        vis = set()
        q = deque([s])
        ans = s
        vis.add(s)
        while q:
            cur = q.popleft()
            if cur < ans:
                ans = cur
            # Add a to odd indices
            t = list(cur)
            for i in range(1, len(t), 2):
                t[i] = str((int(t[i]) + a) % 10)
            tstr = ''.join(t)
            if tstr not in vis:
                vis.add(tstr)
                q.append(tstr)
            # Rotate by b
            tstr = cur[-b:] + cur[:-b]
            if tstr not in vis:
                vis.add(tstr)
                q.append(tstr)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn find_lex_smallest_string(s: String, a: i32, b: i32) -> String {
        use std::collections::{HashSet, VecDeque};
        let mut vis = HashSet::new();
        let mut q = VecDeque::new();
        let mut ans = s.clone();
        q.push_back(s.clone());
        vis.insert(s.clone());
        let n = ans.len();
        while let Some(cur) = q.pop_front() {
            if cur < ans { ans = cur.clone(); }
            let mut t: Vec<u8> = cur.bytes().collect();
            for i in (1..n).step_by(2) {
                t[i] = ((t[i]-b'0'+a as u8)%10 + b'0') as u8;
            }
            let tstr = String::from_utf8(t).unwrap();
            if vis.insert(tstr.clone()) { q.push_back(tstr); }
            let rot = cur[n-b as usize..].to_string() + &cur[..n-b as usize];
            if vis.insert(rot.clone()) { q.push_back(rot); }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    findLexSmallestString(s: string, a: number, b: number): string {
        const vis = new Set<string>();
        const q: string[] = [s];
        let ans = s;
        vis.add(s);
        while (q.length) {
            const cur = q.shift()!;
            if (cur < ans) ans = cur;
            // Add a to odd indices
            const t = cur.split('');
            for (let i = 1; i < t.length; i += 2) t[i] = ((parseInt(t[i]) + a) % 10).toString();
            const tstr = t.join('');
            if (!vis.has(tstr)) { vis.add(tstr); q.push(tstr); }
            // Rotate by b
            const rot = cur.slice(-b) + cur.slice(0, -b);
            if (!vis.has(rot)) { vis.add(rot); q.push(rot); }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(N^2) in the worst case, where N is the length of s (since the number of unique states is bounded by the number of possible strings).
  • 🧺 Space complexity: O(N^2), for the visited set and queue.