LeetCode 1625 - Lexicographically Smallest String After Applying Operations

LeetCode Problem 1625

Difficulty: 🟡 Medium
Topics: String, Depth-First Search, Breadth-First Search, Enumeration

Solution

Problem Understanding

The problem gives us a numeric string s of even length and two operations that can be performed any number of times in any order.

The first operation adds the integer a to every digit located at an odd index. Since digits must remain between 0 and 9, the addition wraps around using modulo 10. For example, if a digit is 8 and we add 5, the result becomes 3.

The second operation rotates the string to the right by b positions. A rotation changes which digits appear at odd and even indices, which is extremely important because the add operation only affects odd indices.

Our task is to find the lexicographically smallest string that can be reached after performing these operations repeatedly.

A lexicographically smaller string is determined the same way words are ordered in a dictionary. We compare characters from left to right, and the first smaller digit determines the smaller string.

The constraints are relatively small:

• s.length <= 100
• Digits only
• Length is always even

Even though the string length is small, the number of operation sequences can become enormous if explored naively. Since operations can be repeated indefinitely, we need a way to avoid revisiting the same states repeatedly.

The important observation is that the number of distinct reachable strings is finite. Each character can only take one of ten values, and rotations are also finite. This naturally suggests graph traversal using Breadth-First Search or Depth-First Search with a visited set.

Several edge cases are important:

• If rotating by b never changes parity positions, some digits may never become modifiable.
• If a and 10 share factors, repeated additions may not generate all digits.
• The original string itself may already be the lexicographically smallest answer.
• When b is odd, rotations can move digits between even and odd positions, allowing all positions to eventually be modified.
• When b is even, only original odd positions can ever be changed.

A correct solution must carefully explore all reachable states without infinite loops.

Approaches

Brute Force Approach

The most direct idea is to recursively try every possible sequence of operations and track the smallest string encountered.

From each state, we can:

1. Apply the add operation.
2. Apply the rotation operation.
3. Continue recursively from both resulting states.

This approach is correct because every possible sequence of operations is eventually explored.

However, the problem is that operations can be repeated forever. Without remembering previously seen states, the search enters cycles immediately. For example, repeated rotations eventually return to the original string.

Even if we add cycle detection, a naive brute force implementation may still repeatedly recompute transformations and explore states inefficiently.

Key Insight

The crucial observation is that the problem forms a graph:

• Each unique string is a node.
• Each operation creates edges to neighboring states.

Since the number of distinct reachable strings is finite, we can perform a graph traversal starting from s.

Breadth-First Search or Depth-First Search both work because we are not minimizing the number of operations. We only need the lexicographically smallest reachable state.

During traversal:

• Maintain a visited set to avoid processing the same string multiple times.

• For every newly discovered state, compare it with the current best answer.

• Generate the two neighboring states:

• Add operation

• Rotate operation

Eventually, all reachable states are explored exactly once.

This transforms an infinite-operation problem into a finite graph traversal problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential / Unbounded	Exponential	Repeatedly explores cycles and operation sequences
Optimal BFS/DFS Graph Traversal	O(N × S)	O(S)	Explores each reachable state once

Where:

• N is the string length
• S is the number of reachable states

Since each state generates two neighbors and string operations cost O(N), the total runtime becomes manageable.

Algorithm Walkthrough

Optimal BFS Algorithm

1. Initialize a queue with the starting string s.

We begin graph traversal from the initial state. 2. Create a visited set and insert s.

This prevents infinite loops and duplicate processing. 3. Initialize the answer as s.

Since the original string is reachable with zero operations, it is our initial candidate. 4. While the queue is not empty, remove the front string.

Each popped string represents a reachable state. 5. Compare the current string with the best answer.

If the current string is lexicographically smaller, update the answer. 6. Generate the string produced by the add operation.

For every odd index:

• Convert the digit to an integer.
• Add a.
• Apply modulo 10.
• Convert back to a character.

7. If the add-generated string has not been visited:

• Add it to visited
• Push it into the queue

8. Generate the rotated string.

Rotate right by b positions using slicing:

• Last b characters move to the front.
• Remaining characters follow afterward.

9. If the rotated string has not been visited:

• Add it to visited
• Push it into the queue

10. Continue until the queue becomes empty.

At this point, every reachable string has been explored. 11. Return the smallest string found.

Why it works

The algorithm works because the operations define a finite state graph. BFS systematically explores every reachable state exactly once using the visited set. Since every reachable string is considered, and we continuously track the lexicographically smallest one, the final answer must be the smallest reachable string.

Python Solution

from collections import deque
from typing import Set

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        def add_operation(current: str) -> str:
            chars = list(current)

            for i in range(1, len(chars), 2):
                digit = (int(chars[i]) + a) % 10
                chars[i] = str(digit)

            return "".join(chars)

        def rotate_operation(current: str) -> str:
            return current[-b:] + current[:-b]

        visited: Set[str] = set([s])
        queue = deque([s])

        smallest = s

        while queue:
            current = queue.popleft()

            if current < smallest:
                smallest = current

            added = add_operation(current)

            if added not in visited:
                visited.add(added)
                queue.append(added)

            rotated = rotate_operation(current)

            if rotated not in visited:
                visited.add(rotated)
                queue.append(rotated)

        return smallest

The implementation follows the graph traversal algorithm directly.

The add_operation helper converts the string into a mutable list so odd-index digits can be updated efficiently. Each digit is incremented by a and wrapped using modulo 10.

The rotate_operation helper uses Python slicing to rotate the string to the right by b positions.

A queue is used for BFS traversal, and the visited set guarantees that every reachable state is processed only once.

During traversal, every current state is compared against the current best answer using normal string comparison, which already performs lexicographical ordering correctly in Python.

Go Solution

package main

func findLexSmallestString(s string, a int, b int) string {
	addOperation := func(current string) string {
		chars := []byte(current)

		for i := 1; i < len(chars); i += 2 {
			digit := int(chars[i]-'0')
			digit = (digit + a) % 10
			chars[i] = byte(digit) + '0'
		}

		return string(chars)
	}

	rotateOperation := func(current string) string {
		n := len(current)
		return current[n-b:] + current[:n-b]
	}

	queue := []string{s}
	visited := map[string]bool{
		s: true,
	}

	smallest := s

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		if current < smallest {
			smallest = current
		}

		added := addOperation(current)

		if !visited[added] {
			visited[added] = true
			queue = append(queue, added)
		}

		rotated := rotateOperation(current)

		if !visited[rotated] {
			visited[rotated] = true
			queue = append(queue, rotated)
		}
	}

	return smallest
}

The Go implementation mirrors the Python solution closely.

Since Go strings are immutable, the add operation converts the string into a byte slice before modifying digits.

The queue is implemented using a slice. Removing the front element is done with queue = queue[1:].

Lexicographical comparison between strings works directly with the < operator in Go, so no custom comparator is needed.

Integer overflow is not a concern because all digit arithmetic remains within small bounds.

Worked Examples

Example 1

Input:

s = "5525"
a = 9
b = 2

Initial state:

Queue	Visited	Smallest
["5525"]	{"5525"}	"5525"

Process "5525":

Operation	Result
Add	"5424"
Rotate	"2555"

Queue becomes:

Queue
["5424", "2555"]

Current smallest:

2555 < 5525

So smallest becomes "2555".

Processing continues, exploring all reachable states.

Eventually BFS reaches:

"2050"

No reachable string is lexicographically smaller.

Final answer:

"2050"

Example 2

Input:

s = "74"
a = 5
b = 1

Initial:

Queue	Smallest
["74"]	"74"

Process "74":

Operation	Result
Add	"79"
Rotate	"47"

Process "47":

Operation	Result
Add	"42"
Rotate	"74"

Process "42":

Operation	Result
Add	"47"
Rotate	"24"

Now "24" becomes the smallest string.

No later state improves upon it.

Final answer:

"24"

Example 3

Input:

s = "0011"
a = 4
b = 2

Rotating by 2 preserves parity positions because the length is 4.

Only odd indices can ever change.

The leading digits remain fixed as "00".

Any addition only increases odd-position digits cyclically, never producing a smaller prefix than "00".

Therefore the original string is already optimal.

Final answer:

"0011"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N × S)	Each reachable state is processed once, and each operation costs O(N)
Space	O(S)	The visited set and queue store reachable states

Here:

• N is the string length
• S is the number of reachable states

The number of reachable states is finite because:

• Each digit has only 10 possibilities
• Rotations are finite

In practice, the state space remains manageable for N <= 100.

Test Cases

sol = Solution()

# Provided examples
assert sol.findLexSmallestString("5525", 9, 2) == "2050"  # example 1
assert sol.findLexSmallestString("74", 5, 1) == "24"  # example 2
assert sol.findLexSmallestString("0011", 4, 2) == "0011"  # example 3

# Smallest possible length
assert sol.findLexSmallestString("10", 1, 1) == "01"  # rotation improves answer

# No improvement possible
assert sol.findLexSmallestString("00", 5, 1) == "00"  # already minimal

# Multiple additions needed
assert sol.findLexSmallestString("19", 1, 1) == "00"  # repeated additions cycle digits

# Even rotation preserves parity
assert sol.findLexSmallestString("1234", 3, 2) == "1032"  # only odd positions modifiable

# Odd rotation allows full flexibility
assert sol.findLexSmallestString("43987654", 7, 3) == "00553311"  # extensive exploration

# Repeated rotations return to original
assert sol.findLexSmallestString("8888", 9, 2) == "8888"  # all states identical

# Large add value
assert sol.findLexSmallestString("1234", 9, 1) == "0022"  # modulo wrapping

# Leading zero creation
assert sol.findLexSmallestString("9090", 1, 1) == "0000"  # can produce all zeros

Test Case Summary

Test	Why
"5525", 9, 2	Validates general BFS exploration
"74", 5, 1	Small input with full rotation flexibility
"0011", 4, 2	Original string already optimal
"10", 1, 1	Smallest valid string length
"00", 5, 1	No operation changes result
"19", 1, 1	Repeated addition cycles through digits
"1234", 3, 2	Even rotation preserves parity
"43987654", 7, 3	Large reachable state graph
"8888", 9, 2	Rotations lead back to identical states
"1234", 9, 1	Tests modulo wraparound
"9090", 1, 1	Tests creation of leading zeros

Edge Cases

One important edge case occurs when b is even. In this situation, rotating the string never changes which indices are odd and which are even. Digits originally at even positions always remain at even positions, meaning they can never be modified by the add operation. A buggy implementation might incorrectly assume every digit can eventually change. The BFS solution handles this naturally because it only explores states actually reachable through legal operations.

Another important case is when repeated additions cycle back to the original digit before reaching every possible digit. For example, if a = 2, repeatedly adding only reaches digits with the same parity. A naive implementation might incorrectly assume all ten digits become reachable. Since the algorithm explicitly generates reachable states rather than making assumptions, it remains correct.

Leading zeros are another subtle case. Lexicographical comparison heavily favors smaller leading digits, so strings beginning with '0' are often optimal. Some implementations accidentally treat the string as an integer and lose leading zeros. This solution always keeps values as strings, preserving correct lexicographical behavior.

A final edge case occurs when operations repeatedly produce the same states. Without a visited set, the search would loop forever. The implementation prevents this by storing every processed state and never revisiting it.