Lexicographically Smallest String After Applying Operations Python/Java solution

Python and Java implementations usually follow the BFS state exploration strategy. Use a queue to process strings, generate the two possible next states, and track visited states with a set. The smallest lexicographic string encountered during traversal is returned as the final answer.

What is the best approach for Lexicographically Smallest String After Applying Operations?

Breadth-First Search over string states is the most common approach. Treat each string as a node and generate neighbors by applying the add and rotate operations. Track visited states to avoid repetition and update the smallest lexicographic string during traversal. Time complexity is O(K * n) where K is the number of reachable configurations.

Is Lexicographically Smallest String After Applying Operations asked at Google/Amazon/Meta?

Variants of this problem appear in interviews at companies like Amazon and Google because it combines string manipulation with state-space search. Interviewers often expect candidates to model operations as graph transitions and use BFS or reasoning about cycles.

What data structure is used in Lexicographically Smallest String After Applying Operations?

The BFS solution primarily uses a queue for traversal and a hash set to track visited strings. These structures prevent revisiting states and ensure each configuration is processed once. String manipulation is used to apply digit addition and rotation operations.

What is the time complexity of Lexicographically Smallest String After Applying Operations?

The BFS approach runs in O(K * n) time where K is the number of reachable string states and n is the string length. Each state requires O(n) time to apply the add or rotate operation. A mathematical cycle optimization reduces exploration to O(n * 10 * (n / gcd(n, b))).

Description Hints 3 Solution Video 30:48

1625. Lexicographically Smallest String After Applying Operations

Q: Is Lexicographically Smallest String After Applying Operations easy or hard?

This problem is typically rated Medium difficulty. The challenge is recognizing that operations form cycles and avoiding infinite exploration. Once modeled as a finite state graph with BFS or cycle enumeration, the implementation becomes manageable.

Q: How to solve Lexicographically Smallest String After Applying Operations in O(n)?

A near-linear solution relies on cycle detection using modular arithmetic. Rotations repeat after n / gcd(n, b) steps and digit additions repeat every 10 operations due to modulo 10. Enumerating these cycles lets you test all valid configurations without storing every state explicitly.

Medium79.4% acceptance2 companies

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' 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 <= 100
s.length is even.
s consists of digits from 0 to 9 only.
1 <= a <= 9
1 <= b <= s.length - 1

Asked at 2 companies

JPMorgan Chase Amazon

Topics

Hints open one at a time

Hint 1

Since the length of s is even, the total number of possible sequences is at most 10 * 10 * s.length.

Hint 2

You can generate all possible sequences and take their minimum.

Hint 3

Keep track of already generated sequences so they are not processed again.

30:48

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution