The trick here is to name the state correctly, then let the implementation follow. For 1625. Lexicographically Smallest String After Applying Operations Medium, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: DFS + memoization, graph traversal, dynamic programming.
The notes already sitting in the source point us in the right direction:
- dfs
- but the traverse is incomplete
- WA
- 43 / 80 test cases passed.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are add, rotate, dfs, findLexSmallestString.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//dfs
02//but the traverse is incomplete
03//WA
04//43 / 80 test cases passed.
05/*
06"31"
074
081
09Expected: "11"
10*/
11class Solution {
12public:
13 int n;
14 unordered_set<string> visited;
15 unordered_map<string, string> memo;
16
17 string add(string& s, int a){
18 string ret = s;
19 for(int i = 1; i < n; i+=2){
20 ret[i] = '0'+(ret[i]-'0'+a)%10;
21 }
22 return ret;
23 }
24
25 string rotate(string& s, int b){
26 string ret = s;
27
28 ret = s.substr(b) + s.substr(0, b);
29
30 return ret;
31 }
32
33 string dfs(string& s, int& a, int& b){
34 if(memo.find(s) != memo.end()){
35 // cout << "memo" << endl;
36 return memo[s];
37 }else if(visited.find(s) != visited.end()){
38 //to jump out of the loop!
39 return "aaaa";
40 }else{
41 visited.insert(s);
42 string sadd = add(s, a);
43 string srot = rotate(s, b);
44
45 // cout << s << ", add: " << sadd << ", rot: " << srot << endl;
46
47 //stop condition
48 if(sadd >= s && srot >= s){
49 memo[s] = s;
50 // cout << s << " is minimum" << endl;
51 return memo[s];
52 }
53
54 memo[s] = min(dfs(sadd, a, b), dfs(srot, a, b));
55
56 // cout << s << " -> " << memo[s] << endl;
57 return memo[s];
58 }
59 }
60
61 string findLexSmallestString(string s, int a, int b) {
62 n = s.size();
63
64 return dfs(s, a, b);
65 }
66};
67
68//dfs, corrected from above
69//Runtime: 592 ms, faster than 29.07% of C++ online submissions for Lexicographically Smallest String After Applying Operations.
70//Memory Usage: 169.2 MB, less than 5.03% of C++ online submissions for Lexicographically Smallest String After Applying Operations.
71class Solution {
72public:
73 int n;
74 unordered_set<string> visited;
75 unordered_map<string, string> memo;
76
77 string add(string& s, int a){
78 string ret = s;
79 for(int i = 1; i < n; i+=2){
80 ret[i] = '0'+(ret[i]-'0'+a)%10;
81 }
82 return ret;
83 }
84
85 string rotate(string& s, int b){
86 string ret = s;
87
88 ret = s.substr(b) + s.substr(0, b);
89
90 return ret;
91 }
92
93 string dfs(string& s, int& a, int& b){
94 if(memo.find(s) != memo.end()){
95 // cout << "memo" << endl;
96 return memo[s];
97 }else if(visited.find(s) != visited.end()){
98 //to jump out of the loop!
99 return "aaaa";
100 }else{
101 visited.insert(s);
102 string sadd = add(s, a);
103 string srot = rotate(s, b);
104
105 // cout << s << ", add: " << sadd << ", rot: " << srot << endl;
106
107 memo[s] = min({s, dfs(sadd, a, b), dfs(srot, a, b)});
108
109 // cout << s << " -> " << memo[s] << endl;
110 return memo[s];
111 }
112 }
113
114 string findLexSmallestString(string s, int a, int b) {
115 n = s.size();
116
117 return dfs(s, a, b);
118 }
119};
120
121//dfs
122//https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations/discuss/899489/Basic-DFS-Brute-force-or-This-kind-of-questions-DFS
123//no early stop make it correct?
124//Runtime: 308 ms, faster than 71.01% of C++ online submissions for Lexicographically Smallest String After Applying Operations.
125//Memory Usage: 91.9 MB, less than 5.13% of C++ online submissions for Lexicographically Smallest String After Applying Operations.
126class Solution {
127public:
128 int n, a, b;
129 unordered_set<string> visited;
130 string ans;
131
132 string add(string& s){
133 string ret = s;
134 for(int i = 1; i < n; i+=2){
135 ret[i] = '0'+(ret[i]-'0'+a)%10;
136 }
137 return ret;
138 }
139
140 string rotate(string& s){
141 string ret = s;
142
143 ret = s.substr(b) + s.substr(0, b);
144
145 return ret;
146 }
147
148 void dfs(string s){
149 if(visited.find(s) != visited.end()) return;
150
151 visited.insert(s);
152 ans = min(ans, s);
153
154 dfs(add(s));
155 dfs(rotate(s));
156 }
157
158 string findLexSmallestString(string s, int a, int b) {
159 n = s.size();
160 this->a = a;
161 this->b = b;
162 ans = "aaaa";
163 dfs(s);
164 return ans;
165 }
166};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.