# 1625. Lexicographically Smallest String After Applying Operations

• Time: $O(n^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public: string findLexSmallestString(string s, int a, int b) { string ans = s; dfs(s, a, b, {}, ans); return ans; } private: void dfs(string s, int a, int b, unordered_set&& seen, string& ans) { if (seen.count(s)) return; seen.insert(s); ans = min(ans, s); dfs(add(s, a), a, b, move(seen), ans); dfs(rotate(s, b), a, b, move(seen), ans); } string add(string& s, int a) { for (int i = 1; i < s.length(); i += 2) s[i] = '0' + (s[i] - '0' + a) % 10; return s; } string rotate(const string& s, int b) { const int n = s.length(); return s.substr(n - b, n) + s.substr(0, n - b); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public String findLexSmallestString(String s, int a, int b) { ans = s; dfs(s, a, b, new HashSet<>()); return ans; } private String ans; private void dfs(String s, int a, int b, Set seen) { if (seen.contains(s)) return; seen.add(s); if (ans.compareTo(s) > 0) ans = s; dfs(add(s, a), a, b, seen); dfs(rotate(s, b), a, b, seen); } private String add(final String s, int a) { StringBuilder sb = new StringBuilder(s); for (int i = 1; i < sb.length(); i += 2) sb.setCharAt(i, (char) ('0' + (s.charAt(i) - '0' + a) % 10)); return sb.toString(); } private String rotate(final String s, int b) { final int n = s.length(); return s.substring(n - b, n) + s.substring(0, n - b); } }