1625. Lexicographically Smallest String After Applying Operations

Problem Description

In this problem, we are given a string s representing a sequence of digits from 0 to 9. The length of s is guaranteed to be even. We are also provided with two integers a and b. Our task is to transform s into the lexicographically smallest possible string by repeatedly applying two types of operations in any order:

Add Operation: We can add the integer a to each digit at an odd index (where indexing starts from 0). If adding a causes the digit to become greater than 9, it wraps around to 0 and continues from there (essentially we take the sum modulo 10).
Rotate Operation: We can rotate the string to the right by b positions. Rotating by b positions means taking the last b characters of s and moving them to the front.

A lexicographically smaller string is defined as one that would come first in a dictionary. For example, '2034' is lexicographically smaller than '2035' because it has a smaller digit ('4' instead of '5') in the last position where they differ.

The aim, therefore, is to find the sequence of operations that, when applied to s, will result in the lexicographically smallest string.

Flowchart Walkthrough

Let's analyze Leetcode 1625. Lexicographically Smallest String After Applying Operations using the Flowchart. We'll determine the appropriate algorithm by working through the flowchart step-by-step:

Is it a graph?

Yes: We can consider each string transformation as a node in a graph, with edges to nodes representing strings obtained by applying the given operations.

Is it a tree?

No: The graph is not necessarily a hierarchical tree, as there can be multiple ways to reach the same string (node), implying it could have cycles.

Is the problem related to directed acyclic graphs (DAGs)?

No: The transformations could lead back to previously visited strings, meaning potential cycles exist, so the graph can't be a DAG.

Is the problem related to shortest paths?

No: The objective is to find the lexicographically smallest string, not the shortest path between two nodes.

Does the problem involve connectivity?

Yes: We need to explore all possible string transformations (connected nodes in the graph space) to find the minimum lexicographical order.

Does the problem have small constraints?

Yes: Considering the operations and their effects can be bounded by the length and structure of the string and operations themselves, we might assume manageably small constraints for exploration.

Conclusion: According to the flowchart, since the problem involves working with small constraints and exploring connectivity without concerns about weights, Breadth-First Search (BFS) is apropos. BFS will help efficiently explore all reachable configurations by systematically visiting strings and their neighbors (reachable via the defined operations), which suits the required exhaustive examination for this problem.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The challenge of this problem lies in determining the correct order and amount of operations to apply since both rotate and add operations can be done an unlimited number of times. The brute force approach of trying every possible combination of operations is not feasible due to the potentially massive number of combinations.

Since s is of an even length, there are two distinct cases for the rotate operation:

If b is even, rotating the string does not change the positions of the odd and even indexed characters relative to each other.
If b is odd, each rotation swaps the positions of odd and even indexed characters.

Given these properties, we can infer a few strategies that help reduce the problem space:

Rotating the string by its length n or a multiple of it returns the string to its original configuration. Thus, we need to rotate the string at most n-1 times to explore all unique configurations.
Since rotating by an even b doesn't change the relative positions of characters, we only need to focus on applying the add operation to odd indices when b is even.
However, when b is odd, because rotating changes the parity of the indices, we will need to apply the add operation to all characters, both at odd and even positions.

The solution provided employs a breadth-first search (BFS) type of approach. Here are the steps:

Apply the rotation operation one step at a time, each time attempting to compute a lexicographically smaller result.
After each rotate, apply the add operation repeatedly (up to 10 times because after 10 additions we will have cycled through all possible digit values) to the odd indexed characters, checking each time if a smaller string is achieved.
If the rotation step is such that b is odd, extend the same add operation to even indexed characters.

By repeatedly applying this sequence of operations, we ensure that we explore all possible combinations of rotations and additions without redundancy. We keep track of the smallest string seen so far and update this minimum whenever we find a smaller one.

This process is guaranteed to terminate because there are a finite number of possible strings (since s is of finite length), and every step is designed to make progress towards a lexicographically smaller string.

Learn more about Breadth-First Search patterns.

Solution Approach

The solution provided adopts a method similar to breadth-first search (BFS). In graph theory, BFS is an algorithm for traversing or searching tree or graph data structures. It starts at an arbitrary node and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. In our case, the nodes represent different versions of the string we obtain after each rotation and addition operation.

Here's how the solution works:

We initialize ans with the original string s. This will hold the smallest string found during the search.
The variable n stores the length of the string.
A Python list s is created from the original string to allow for mutable operations.
There is an outer loop that permits us to try every possible rotation on the string. We can cycle through all the rotations by rotating one step at a time, up to n times.
The state of s is adjusted with s = s[-b:] + s[:-b]. This line effectively rotates the string to the right by b positions.
An inner loop (ranging from 0 to 9) applies the addition operation to all odd indices of s. This is done 10 times because after 10 additions, the character would have been incremented by a ten times, which is equivalent to adding 0 considering the modulo operation.
If the shift b is odd (b & 1), we account for the switch between the odd and even indices due to the rotations. Yet another nested loop runs for 10 iterations to apply the addition operation to what were originally even indices before rotation.
After each application of the addition operation, we join the characters into a string t using ''.join(s) and compare it with ans. If t is lexicographically smaller than ans, we update ans.
Finally, after all possible transformations are tried, we return ans.

BFS can be a quite wide exploration, but in this algorithm, we are keeping only one copy of the string at each level of depth, rather than exploring multiple strings in parallel. This is an efficient way to handle the problem since we are always iterating from the current smallest string and, by domain constraints, we know there's no need to revisit a string we have already considered.

The Python list structure allows us to perform rotates and additions very efficiently, which is key in handling possibly numerous iterations. The algorithm effectively traverses a space of n * 10 * 10 possible strings (where n is the number of rotations and 10 comes from the number of potential additions to both odd and even indices), ensuring that we find the lexicographically smallest string possible.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a simple example to demonstrate the solution approach. Suppose we are given a string s = "4625", and integers a = 3, and b = 2.

The string s is of length 4, which is even, and we see that the rotation parameter b is also even. Hence, rotating the string will not change odd and even positions relative to each other. Let's follow the steps outlined in the solution approach:

Start with ans = "4625", the original string s.
The length of the string n = 4.

We begin with the outer loop, attempting all possible rotations:

First Rotation: s = "2546" (rotated right by b=2)
- Add a=3 to each digit at odd indices (indexing starts at 0):
  - Apply addition operation: s[1] = (5 + 3) % 10 = 8 and s[3] = (6 + 3) % 10 = 9. Now s = "2849".
  - Update ans since "2849" is lexicographically smaller than "4625".
- As b is even, we don't need to perform addition on even indices this round.
Second Rotation: s = "4928" (rotated right again by b=2 from original, so it is "2546" -> "4928")
- Add a=3 to each digit at the odd indices:
  - Apply addition operation: s[1] = (9 + 3) % 10 = 2 and s[3] = (8 + 3) % 10 = 1. Now s = "4212".
  - Update ans since "4212" is lexicographically smaller than "2849".
- As b is even, we skip addition to even indices again.
Third Rotation: s = "1249" (rotated right again by b=2 from original, so it is "4625" -> "1249")
- Add a=3 to each digit at the odd indices:
  - Apply addition operation: s[1] = (2 + 3) % 10 = 5 and s[3] = (9 + 3) % 10 = 2. Now s = "1522".
  - ans remains "4212" because "1522" is not lexicographically smaller.
Fourth Rotation: s = "2149" (rotated right again by b=2 from original, so it is "4625" -> "2149")
- Add a=3 to each digit at the odd indices:
  - Apply addition operation: s[1] = (1 + 3) % 10 = 4 and s[3] = (9 + 3) % 10 = 2. Now s = "2422".
  - ans remains "4212" because "2422" is not lexicographically smaller.
After the loop completes, we have tried all rotations and addition operations. Our ans holds the lexicographically smallest string: "4212".

Thus, following the BFS-like strategy, we have successfully explored all the possible rotations and have applied addition operations to find the smallest string through efficient updating. The final answer is "4212".

Solution Implementation

1class Solution:
2    def find_lex_smallest_string(self, s: str, a: int, b: int) -> str:
3        # Initialize answer with the initial string.
4        answer = s
5        # Get the length of the input string.
6        n = len(s)
7        # Convert the string to a list for easier manipulation.
8        s = list(s)
9        # Change the string n times, which ensures that
10        # all rotations are visited.
11        for _ in range(n):
12            # Rotate the string based on the value of b.
13            s = s[-b:] + s[:-b]
14            # Add 'a' to every digit at odd indices.
15            for _ in range(10):  # Repeat this operation up to 10 times, one for each digit.
16                for k in range(1, n, 2):
17                    s[k] = str((int(s[k]) + a) % 10)
18                # If 'b' is odd, addition is also applicable at even indices,
19                # since rotation places previously odd indexed numbers at even indices.
20                if b % 2 == 1:
21                    for _ in range(10):  # Repeat for even indices.
22                        for k in range(0, n, 2):
23                            s[k] = str((int(s[k]) + a) % 10)
24                        # Join the list to form a string and compare with the answer.
25                        current = ''.join(s)
26                        # Update the answer if the current string is lexicographically smaller.
27                        if answer > current:
28                            answer = current
29                # If 'b' is even, only update based on odd indices' additions.
30                else:
31                    current = ''.join(s)
32                    if answer > current:
33                        answer = current
34        # Return the lexicographically smallest string obtained.
35        return answer
36

1class Solution {
2    public String findLexSmallestString(String s, int a, int b) {
3        // The length of the string s
4        int lengthOfS = s.length();
5        // The variable 'answer' will hold the lexicographically smallest string found
6        String answer = s;
7      
8        // Rotating the string s for 'lengthOfS' times
9        for (int i = 0; i < lengthOfS; ++i) {
10            // Perform rotation by 'b' characters to the left
11            s = s.substring(b) + s.substring(0, b);
12            // Convert string s to a character array for manipulation
13            char[] charArray = s.toCharArray();
14          
15            // Try adding 'a' to every digit (10 times since there are only 10 possibilities for a digit)
16            for (int j = 0; j < 10; ++j) {
17                // Only add to odd indexed characters of the array starting from 1
18                for (int k = 1; k < lengthOfS; k += 2) {
19                    charArray[k] = (char) (((charArray[k] - '0' + a) % 10) + '0');
20                }
21              
22                // If 'b' is odd, we need to handle even indexed characters as well because rotation affects them
23                if ((b & 1) == 1) {
24                    for (int p = 0; p < 10; ++p) {
25                        // This time add 'a' to even indexed characters
26                        for (int k = 0; k < lengthOfS; k += 2) {
27                            charArray[k] = (char) (((charArray[k] - '0' + a) % 10) + '0');
28                        }
29                        // Create new string from the character array
30                        s = String.valueOf(charArray);
31                        // Update the answer if a new lexicographically smaller string is found
32                        if (answer.compareTo(s) > 0) {
33                            answer = s;
34                        }
35                    }
36                } else {
37                    // If 'b' is even, create a new string and potentially update the answer
38                    s = String.valueOf(charArray);
39                    if (answer.compareTo(s) > 0) {
40                        answer = s;
41                    }
42                }
43            }
44        }
45        // Return the lexicographically smallest string found
46        return answer;
47    }
48}
49

1class Solution {
2public:
3    string findLexSmallestString(string s, int a, int b) {
4        int stringLength = s.size();             // Length of the string.
5        string smallestLexString = s;            // The lexically smallest string found so far.
6      
7        // Perform rotation and replacement operations to find the smallest lexicographical string.
8        for (int i = 0; i < stringLength; ++i) {
9            // Rotate the string by 'b' positions.
10            s = s.substr(stringLength - b) + s.substr(0, stringLength - b);
11          
12            // Try incrementing the digits at odd indices and finding the smallest string.
13            for (int j = 0; j < 10; ++j) {
14                // Increment each digit at odd index 'k' by 'a', and handle wrap around using modulo 10.
15                for (int k = 1; k < stringLength; k += 2) {
16                    s[k] = ((s[k] - '0' + a) % 10) + '0';
17                }
18              
19                // Check if 'b' is odd, if yes, also increment the digits at even indices.
20                if (b % 2 == 1) {
21                    for (int p = 0; p < 10; ++p) {
22                        // Increment each digit at even index 'k' by 'a', and handle wrap around using modulo 10.
23                        for (int k = 0; k < stringLength; k += 2) {
24                            s[k] = ((s[k] - '0' + a) % 10) + '0';
25                        }
26                        // Update smallestLexString if current string 's' is smaller.
27                        smallestLexString = min(smallestLexString, s);
28                    }
29                } else {
30                    // Update smallestLexString if current string 's' is smaller.
31                    smallestLexString = min(smallestLexString, s);
32                }
33            }
34        }
35      
36        // Return the lexically smallest string after trying all possibilities.
37        return smallestLexString;
38    }
39};
40

1// Define the string length variable globally.
2let stringLength: number;
3
4// Function to find the lexicographically smallest string after applying rotation and addition operations.
5function findLexSmallestString(s: string, a: number, b: number): string {
6    stringLength = s.length; // Set the length of the string.
7    let smallestLexString: string = s; // Initialize the smallest lexicographical string found with the original string.
8
9    // Perform rotation and increment operations to find the smallest lexicographical string.
10    for (let i = 0; i < stringLength; ++i) {
11        // Rotate the string by 'b' positions.
12        s = s.substring(stringLength - b) + s.substring(0, stringLength - b);
13
14        // Try incrementing the digits at odd indices and find the smallest string.
15        for (let j = 0; j < 10; ++j) {
16            // Increment each digit at odd indices by 'a', using modulo 10 for wrap around.
17            for (let k = 1; k < stringLength; k += 2) {
18                let digit = (parseInt(s[k]) + a) % 10;
19                s = s.substring(0, k) + digit.toString() + s.substring(k + 1);
20            }
21
22            // If 'b' is odd, also apply incrementation to digits at even indices.
23            if (b % 2 === 1) {
24                for (let p = 0; p < 10; ++p) {
25                    // Increment each digit at even indices by 'a', using modulo 10 for wrap around.
26                    for (let k = 0; k < stringLength; k += 2) {
27                        let digit = (parseInt(s[k]) + a) % 10;
28                        s = s.substring(0, k) + digit.toString() + s.substring(k + 1);
29                    }
30                    // Update smallestLexString if current string 's' is smaller.
31                    smallestLexString = minLexString(smallestLexString, s);
32                }
33            } else {
34                // Update smallestLexString if current string 's' is smaller.
35                smallestLexString = minLexString(smallestLexString, s);
36            }
37        }
38    }
39
40    // Return the lexically smallest string after trying all possibilities.
41    return smallestLexString;
42}
43
44// Helper function to find the smaller of two lexicographically ordered strings.
45function minLexString(str1: string, str2: string): string {
46    return str1.localeCompare(str2) < 0 ? str1 : str2;
47}
48

Time and Space Complexity

Time Complexity

The given code performs a series of rotations and digit increments to find the lexicographically smallest string that can be achieved under given operations. The time complexity can be broken down into multiple parts:

The outermost loop runs at most n times where n is the length of the string, since that's the number of possible rotations we can check.
For every rotation, we have an inner loop running 10 times to increment the digits at odd indices.
When b is odd, an additional loop over 10 iterations is executed for each of the outer loop iterations to increase the even indices.
Within the second and third bullet point loops, there is an iteration over the characters of the string in steps, which is O(n).

Considering these nested loops and their iteration counts, the time complexity can be calculated as follows:

If b is even, the complexity is O(n * 10 * n) = O(n^2) because the changes are applied to odd indices regardless of the number of rotation.
If b is odd, we must consider additional inner iterations for increasing even indices, which adds another factor of 10, leading to O(n * 10 * 10 * n) = O(100 * n^2) = O(n^2), as constant factors are dropped in time complexity considerations.

As the b being even or odd determines whether the innermost loop is executed, the overall time complexity is O(n^2).

Space Complexity

The space complexity of the code is primarily due to the storage of the string s as a list and the temporary storage of the modified string t.

The list converted string takes O(n) space.
The temporary string t also takes O(n) space.

There is no additional space used that grows with the input, as the loops use a constant amount of space. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know