Skip to content

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<string>&& seen, string& ans) {
    if (seen.contains(s))
      return;

    seen.insert(s);
    ans = min(ans, s);

    dfs(add(s, a), a, b, std::move(seen), ans);
    dfs(rotate(s, b), a, b, std::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<String> 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);
  }
}