Input: s ="daily", k =1Output: "ailyd"Explanation:
With k=1, we can only move the first character to the end.Starting: "daily"Move 'd' to end:"ailyd"This is the lexicographically smallest we can achieve.
Input: s ="dcba", k =2Output: "abcd"Explanation:
With k=2, we can move either the first or second character to the end.Starting: "dcba"Move 'd' to end:"cbad"Move 'c' to end:"badc"Move 'b' to end:"adcb"Move 'a' to end:"dcba"(back to start)But we can also:Starting: "dcba"Move 'c' to end:"dbac"Move 'd' to end:"bacd"Move 'b' to end:"acdb"Move 'a' to end:"cdba"Continue optimally to get:"abcd"
Input: s ="cba", k =1Output: "acb"Explanation:
With k=1, we can only move the first character to the end.Starting: "cba"Move 'c' to end:"bac"Move 'b' to end:"acb"Move 'a' to end:"cba"(cycle back)The smallest achievable is"acb".
Input: s ="edcba", k =4Output: "abcde"Explanation:
With k=4, we can move any of the first 4 characters to the end.Through optimal moves, we can arrange the string in sorted order:"abcde".
Since we can perform unlimited moves and each move is deterministic (move one of first k characters to end), we can simulate all possible states reachable from the initial string. We use a set to track visited states to avoid infinite loops and find the lexicographically smallest string among all reachable states.
classSolution {
public: string smallestString(string s, int k) {
unordered_set<string> visited;
queue<string> q;
string ans = s;
q.push(s);
visited.insert(s);
while (!q.empty()) {
string curr = q.front();
q.pop();
if (curr < ans) {
ans = curr;
}
// Try moving each of the first k characters to the end
for (int i =0; i < min(k, (int)curr.length()); i++) {
string next = curr.substr(1, i) + curr.substr(i +1) + curr[i];
if (visited.find(next) == visited.end()) {
visited.insert(next);
q.push(next);
}
}
}
return ans;
}
};
classSolution {
public String smallestString(String s, int k) {
Set<String> visited =new HashSet<>();
Queue<String> queue =new LinkedList<>();
String ans = s;
queue.offer(s);
visited.add(s);
while (!queue.isEmpty()) {
String curr = queue.poll();
if (curr.compareTo(ans) < 0) {
ans = curr;
}
// Try moving each of the first k characters to the endfor (int i = 0; i < Math.min(k, curr.length()); i++) {
String next = curr.substring(1, i + 1) + curr.substring(i + 1) + curr.charAt(i);
if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
return ans;
}
}
classSolution:
defsmallest_string(self, s: str, k: int) -> str:
visited = set()
queue = [s]
ans = s
visited.add(s)
while queue:
curr = queue.pop(0)
if curr < ans:
ans = curr
# Try moving each of the first k characters to the endfor i in range(min(k, len(curr))):
next_str = curr[1:i+1] + curr[i+1:] + curr[i]
if next_str notin visited:
visited.add(next_str)
queue.append(next_str)
return ans
When k >= n, we can move any character to any position, so we can sort the string. When k < n, we’re essentially looking for the lexicographically smallest rotation that’s reachable by our limited moves. We can optimize by recognizing that we’re performing a form of constrained rotation.
classSolution {
public: string smallestStringOptimized(string s, int k) {
int n = s.length();
// If k >= n, we can arrange characters in any order
if (k >= n) {
sort(s.begin(), s.end());
return s;
}
string ans = s;
set<string> reachable;
// Generate all reachable strings using constraint
function<void(string)> generate = [&](string curr) {
if (reachable.count(curr)) return;
reachable.insert(curr);
if (curr < ans) {
ans = curr;
}
// Try moving each of first k characters to end
for (int i =0; i < min(k, n); i++) {
string next = curr.substr(1, i) + curr.substr(i +1) + curr[i];
if (!reachable.count(next)) {
generate(next);
}
}
};
generate(s);
return ans;
}
};
classSolution {
private String ans;
private Set<String> reachable;
public String smallestStringOptimized(String s, int k) {
int n = s.length();
// If k >= n, we can arrange characters in any orderif (k >= n) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
returnnew String(chars);
}
ans = s;
reachable =new HashSet<>();
generate(s, k, n);
return ans;
}
privatevoidgenerate(String curr, int k, int n) {
if (reachable.contains(curr)) return;
reachable.add(curr);
if (curr.compareTo(ans) < 0) {
ans = curr;
}
// Try moving each of first k characters to endfor (int i = 0; i < Math.min(k, n); i++) {
String next = curr.substring(1, i + 1) + curr.substring(i + 1) + curr.charAt(i);
if (!reachable.contains(next)) {
generate(next, k, n);
}
}
}
}
classSolution:
defsmallest_string_optimized(self, s: str, k: int) -> str:
n = len(s)
# If k >= n, we can arrange characters in any orderif k >= n:
return''.join(sorted(s))
self.ans = s
reachable = set()
defgenerate(curr: str) ->None:
if curr in reachable:
return reachable.add(curr)
if curr < self.ans:
self.ans = curr
# Try moving each of first k characters to endfor i in range(min(k, n)):
next_str = curr[1:i+1] + curr[i+1:] + curr[i]
if next_str notin reachable:
generate(next_str)
generate(s)
return self.ans
For certain values of k and string patterns, we can mathematically determine the optimal result without exhaustive search. When k=1, we’re essentially performing rotations. When k is large, we approach full sorting capability. We can identify patterns and shortcuts.
classSolution:
defsmallest_string_pattern(self, s: str, k: int) -> str:
n = len(s)
if k >= n:
return''.join(sorted(s))
if k ==1:
# Find lexicographically smallest rotation doubled = s + s
min_rotation = s
for i in range(1, n):
rotation = doubled[i:i+n]
if rotation < min_rotation:
min_rotation = rotation
return min_rotation
# For general k, use limited search visited = set()
candidates = []
defdfs(curr: str, depth: int) ->None:
if depth >20or curr in visited: # Limit depthreturn visited.add(curr)
candidates.append(curr)
for i in range(min(k, n)):
next_str = curr[1:i+1] + curr[i+1:] + curr[i]
if next_str notin visited:
dfs(next_str, depth +1)
dfs(s, 0)
return min(candidates)