LeetCode 1625: Lexicographically Smallest String After Applying Operations
Problem Description
Explanation
To solve this problem, we can try all possible combinations of applying the two operations: rotating the string and adding 'a' to odd indices. We can use a breadth-first search (BFS) approach to explore all possible states of the string and then return the lexicographically smallest string obtained.
- Start with the initial string 's' and add it to a queue.
- For each string in the queue, apply both operations (rotate and add) to generate new strings.
- Keep track of visited strings to avoid loops and also maintain the lexicographically smallest string found.
- Continue this process until all possible combinations are explored or until we reach the lexicographically smallest string.
Time Complexity: O(n^2 * m^2), where n is the length of the string 's' and m is the number of unique states that can be generated by rotating or adding 'a'. Space Complexity: O(n^2 * m^2) for the queue and visited set.
Solutions
class Solution {
public String findLexSmallestString(String s, int a, int b) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
String smallest = s;
queue.offer(s);
while (!queue.isEmpty()) {
String current = queue.poll();
if (smallest.compareTo(current) > 0) {
smallest = current;
}
String rotated = rotate(current, b);
if (!visited.contains(rotated)) {
visited.add(rotated);
queue.offer(rotated);
}
String added = add(current, a);
if (!visited.contains(added)) {
visited.add(added);
queue.offer(added);
}
}
return smallest;
}
private String rotate(String s, int b) {
return s.substring(s.length() - b) + s.substring(0, s.length() - b);
}
private String add(String s, int a) {
char[] chars = s.toCharArray();
for (int i = 1; i < s.length(); i += 2) {
int num = Character.getNumericValue(chars[i]) + a;
chars[i] = (char) ('0' + num % 10);
}
return new String(chars);
}
}Loading editor...