Lexicographically Smallest String After Applying Operations

Medium
1698.

Lexicographically Smallest String After Applying Operations

Lexicographically Smallest String After Applying Operations is a medium coding problem on strings, depth-first search and breadth-first search, asked in Amazon interviews.

You are given a string s of even length made of digits 0–9, and two integers a and b. You may apply either operation any number of times, in any order:

  • Add: add a to every digit at an odd index (0-indexed); a digit past 9 wraps around to 0. For example, s = "3456" with a = 5 becomes "3951".
  • Rotate: rotate s to the right by b positions. For example, s = "3456" with b = 1 becomes "6345".

Return the lexicographically smallest string you can obtain.

Example 1

Input
s = "5525", a = 9, b = 2
Output
2050
Explanation
Rotate to "2555", add to get "2454", add again to "2353", rotate to "5323", then add repeatedly: "5222", "5121", "5020"; rotate to "2050".

Example 2

Input
s = "74", a = 5, b = 1
Output
24
Explanation
Rotate to "47", add to get "42", rotate to "24".

Example 3

Input
s = "0011", a = 4, b = 2
Output
0011
Explanation
Nothing beats the starting string.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} a
 * @param {number} b
 * @return {string}
 */
var findLexSmallestString = function(s, a, b) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Lexicographically Smallest String After Applying Operations Solution

Lexicographically Smallest String After Applying Operations solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Lexicographically Smallest String After Applying Operations is a medium coding problem on strings, depth-first search and breadth-first search, asked in Amazon interviews.

Problem statement

You are given a string s of even length made of digits 0–9, and two integers a and b. You may apply either operation any number of times, in any order:

  • Add: add a to every digit at an odd index (0-indexed); a digit past 9 wraps around to 0. For example, s = "3456" with a = 5 becomes "3951".
  • Rotate: rotate s to the right by b positions. For example, s = "3456" with b = 1 becomes "6345".

Return the lexicographically smallest string you can obtain.

Example 1

Input: s = "5525", a = 9, b = 2
Output: 2050
Explanation: Rotate to "2555", add to get "2454", add again to "2353", rotate to "5323", then add repeatedly: "5222", "5121", "5020"; rotate to "2050".

Example 2

Input: s = "74", a = 5, b = 1
Output: 24
Explanation: Rotate to "47", add to get "42", rotate to "24".

Example 3

Input: s = "0011", a = 4, b = 2
Output: 0011
Explanation: Nothing beats the starting string.

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

Hints for Lexicographically Smallest String After Applying Operations

  1. Hint 1

    Every reachable string is a state, and the two operations are its edges. How many states can there be?

  2. Hint 2

    Rotations give at most n arrangements, and the digits at odd positions can only be shifted by one of 10 amounts (with even positions too, if b is odd) — at most 100 · n strings in all.

  3. Hint 3

    So just explore everything: BFS or DFS from s with a visited set, and keep the smallest string seen.

How to solve Lexicographically Smallest String After Applying Operations

The space of reachable strings is small — at most n rotations times 10 shifts of the odd positions (times 10 for the even positions when b is odd) — so an exhaustive search over it is fast and obviously correct.

Approach

  1. Start a queue and a visited set with s; let best = s.
  2. Pop a string, update best if it is smaller.
  3. Generate its two neighbours — the add result and the rotate result — and push each one not yet visited.
  4. When the queue is empty, return best.

Why it works

The search visits exactly the strings reachable from s by any sequence of operations, so the minimum over them is the answer. Adding a ten times returns the digits to where they started and rotating returns after n / gcd(n, b) steps, which is why the set of states is finite and bounded by about 100 · n.

Complexity

  • Time — O(100 · n^2) — up to 100·n states, each copied in O(n)
  • Space — O(100 · n^2)

Pitfalls

  • "Odd indices" are 1, 3, 5, … counting from 0, not the 1st, 3rd, … characters.
  • When b is even, rotation keeps odd positions odd, so even-index digits never change; when b is odd they can be shifted too. The search handles both without special cases.
  • Compare strings lexicographically, not as numbers — leading zeros matter.

Reference solution

Python

from collections import deque

def findLexSmallestString(s: str, a: int, b: int) -> str:
    n = len(s)
    seen = {s}
    q = deque([s])
    best = s
    while q:
        cur = q.popleft()
        if cur < best:
            best = cur
        added = ''.join(str((int(ch) + a) % 10) if i % 2 else ch for i, ch in enumerate(cur))
        rotated = cur[n - b:] + cur[:n - b]
        for t in (added, rotated):
            if t not in seen:
                seen.add(t)
                q.append(t)
    return best

Java

public static String findLexSmallestString(String s, int a, int b) {
    int n = s.length();
    Set<String> seen = new HashSet<>();
    ArrayDeque<String> q = new ArrayDeque<>();
    seen.add(s);
    q.add(s);
    String best = s;
    while (!q.isEmpty()) {
        String cur = q.poll();
        if (cur.compareTo(best) < 0) best = cur;
        char[] chars = cur.toCharArray();
        for (int i = 1; i < n; i += 2) chars[i] = (char) ('0' + (chars[i] - '0' + a) % 10);
        String added = new String(chars);
        String rotated = cur.substring(n - b) + cur.substring(0, n - b);
        if (seen.add(added)) q.add(added);
        if (seen.add(rotated)) q.add(rotated);
    }
    return best;
}

C++

string findLexSmallestString(string s, int a, int b) {
    int n = s.size();
    unordered_set<string> seen{s};
    queue<string> q;
    q.push(s);
    string best = s;
    while (!q.empty()) {
        string cur = q.front(); q.pop();
        if (cur < best) best = cur;
        string added = cur;
        for (int i = 1; i < n; i += 2) added[i] = '0' + (added[i] - '0' + a) % 10;
        string rotated = cur.substr(n - b) + cur.substr(0, n - b);
        if (seen.insert(added).second) q.push(added);
        if (seen.insert(rotated).second) q.push(rotated);
    }
    return best;
}

JavaScript

var findLexSmallestString = function(s, a, b) {
    var n = s.length, seen = {}, q = [s], best = s;
    seen[s] = true;
    for (var h = 0; h < q.length; h++) {
        var cur = q[h];
        if (cur < best) best = cur;
        var chars = cur.split("");
        for (var i = 1; i < n; i += 2) chars[i] = String((chars[i].charCodeAt(0) - 48 + a) % 10);
        var added = chars.join("");
        var rotated = cur.substring(n - b) + cur.substring(0, n - b);
        if (!seen[added]) { seen[added] = true; q.push(added); }
        if (!seen[rotated]) { seen[rotated] = true; q.push(rotated); }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Depth-First Search (DFS)