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.
- Difficulty: Medium
- Topics: Strings, Depth-First Search, Breadth-First Search, Enumeration
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
ato every digit at an odd index (0-indexed); a digit past9wraps around to0. For example,s = "3456"witha = 5becomes"3951". - Rotate: rotate
sto the right bybpositions. For example,s = "3456"withb = 1becomes"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 <= 100s.length is evens consists of digits from 0 to 9 only1 <= a <= 91 <= b <= s.length - 1
Hints for Lexicographically Smallest String After Applying Operations
Hint 1
Every reachable string is a state, and the two operations are its edges. How many states can there be?
Hint 2
Rotations give at most
narrangements, and the digits at odd positions can only be shifted by one of 10 amounts (with even positions too, ifbis odd) — at most100 · nstrings in all.Hint 3
So just explore everything: BFS or DFS from
swith 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
- Start a queue and a visited set with
s; letbest = s. - Pop a string, update
bestif it is smaller. - Generate its two neighbours — the add result and the rotate result — and push each one not yet visited.
- 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
bis even, rotation keeps odd positions odd, so even-index digits never change; whenbis 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 bestJava
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)