Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using core interview patterns strategy.
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:
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".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 <= 100s.length is even.s consists of digits from 0 to 9 only.1 <= a <= 91 <= b <= s.length - 1Problem summary: 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'
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: General problem-solving
"5525" 9 2
"74" 5 1
"0011" 4 2
lexicographically-smallest-string-after-substring-operation)lexicographically-smallest-string-after-a-swap)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1625: Lexicographically Smallest String After Applying Operations
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;
}
}
// Accepted solution for LeetCode #1625: Lexicographically Smallest String After Applying Operations
func findLexSmallestString(s string, a int, b int) string {
q := []string{s}
vis := map[string]bool{s: true}
ans := s
n := len(s)
for len(q) > 0 {
s = q[0]
q = q[1:]
if ans > s {
ans = s
}
t1 := []byte(s)
for i := 1; i < n; i += 2 {
t1[i] = byte((int(t1[i]-'0')+a)%10 + '0')
}
t2 := s[n-b:] + s[:n-b]
for _, t := range []string{string(t1), t2} {
if !vis[t] {
vis[t] = true
q = append(q, t)
}
}
}
return ans
}
# Accepted solution for LeetCode #1625: Lexicographically Smallest String After Applying Operations
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
// Accepted solution for LeetCode #1625: Lexicographically Smallest String After Applying Operations
struct Solution;
use std::collections::HashSet;
use std::collections::VecDeque;
impl Solution {
fn find_lex_smallest_string(s: String, a: i32, b: i32) -> String {
let n = s.len();
let a = a as u8;
let b = b as usize;
let s: Vec<u8> = s.bytes().map(|b| b - b'0').collect();
let mut visited: HashSet<Vec<u8>> = HashSet::new();
let mut queue: VecDeque<Vec<u8>> = VecDeque::new();
visited.insert(s.clone());
queue.push_back(s.clone());
let mut min = s;
while let Some(first) = queue.pop_front() {
if first < min {
min = first.clone();
}
let mut rotated = first.clone();
let plus = Self::add(first, a, n);
rotated.rotate_right(b);
if visited.insert(plus.clone()) {
queue.push_back(plus);
}
if visited.insert(rotated.clone()) {
queue.push_back(rotated);
}
}
let mut res = "".to_string();
for b in min {
res.push((b + b'0') as char);
}
res
}
fn add(mut s: Vec<u8>, a: u8, n: usize) -> Vec<u8> {
for i in 0..n {
if i % 2 == 1 {
s[i] += a;
s[i] %= 10;
}
}
s
}
}
#[test]
fn test() {
let s = "5525".to_string();
let a = 9;
let b = 2;
let res = "2050".to_string();
assert_eq!(Solution::find_lex_smallest_string(s, a, b), res);
let s = "74".to_string();
let a = 5;
let b = 1;
let res = "24".to_string();
assert_eq!(Solution::find_lex_smallest_string(s, a, b), res);
let s = "0011".to_string();
let a = 4;
let b = 2;
let res = "0011".to_string();
assert_eq!(Solution::find_lex_smallest_string(s, a, b), res);
let s = "43987654".to_string();
let a = 7;
let b = 3;
let res = "00553311".to_string();
assert_eq!(Solution::find_lex_smallest_string(s, a, b), res);
}
// Accepted solution for LeetCode #1625: Lexicographically Smallest String After Applying Operations
function findLexSmallestString(s: string, a: number, b: number): string {
const q: string[] = [s];
const vis = new Set<string>([s]);
let ans = s;
let i = 0;
while (i < q.length) {
s = q[i++];
if (ans > s) {
ans = s;
}
const t1 = s
.split('')
.map((c, j) => (j & 1 ? String((Number(c) + a) % 10) : c))
.join('');
const t2 = s.slice(-b) + s.slice(0, -b);
for (const t of [t1, t2]) {
if (!vis.has(t)) {
vis.add(t);
q.push(t);
}
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.