1625. Lexicographically Smallest String After Applying Operations LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1625. Lexicographically Smallest String After Applying Operations LeetCode Solution with the best time and space complexity. The solution to Lexicographically Smallest String After Applying Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Lexicographically Smallest String After Applying Operations solution in C++
Lexicographically Smallest String After Applying Operations solution in Java
Lexicographically Smallest String After Applying Operations solution in Python
Additional Resources

1625. Lexicographically Smallest String After Applying Operations LeetCode Solution image

Problem Statement of Lexicographically Smallest String After Applying Operations

You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b.
You can apply either of the following two operations any number of times and in any order on s:

Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. For example, if s = “3456” and a = 5, s becomes “3951”.
Rotate s to the right by b positions. For example, if s = “3456” and b = 1, s becomes “6345”.

Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s.
A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, “0158” is lexicographically smaller than “0190” because the first position they differ is at the third letter, and ‘5’ comes before ‘9’.

Example 1:

Input: s = “5525”, a = 9, b = 2
Output: “2050”
Explanation: We can apply the following operations:
Start: “5525”
Rotate: “2555”
Add: “2454”
Add: “2353”
Rotate: “5323”
Add: “5222”
Add: “5121”
Rotate: “2151”
Add: “2050”
There is no way to obtain a string that is lexicographically smaller than “2050”.

Example 2:

Input: s = “74”, a = 5, b = 1
Output: “24”
Explanation: We can apply the following operations:
Start: “74”
Rotate: “47”
Add: “42”
Rotate: “24”
There is no way to obtain a string that is lexicographically smaller than “24”.

Example 3:

Input: s = “0011”, a = 4, b = 2
Output: “0011”
Explanation: There are no sequence of operations that will give us a lexicographically smaller string than “0011”.

Constraints:

2 <= s.length <= 100
s.length is even.
s consists of digits from 0 to 9 only.
1 <= a <= 9
1 <= b <= s.length – 1

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n)

1625. Lexicographically Smallest String After Applying Operations LeetCode Solution in C++

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);
  }
};
/* code provided by PROGIEZ */

1625. Lexicographically Smallest String After Applying Operations LeetCode Solution in Java

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);
  }
}
// code provided by PROGIEZ

1625. Lexicographically Smallest String After Applying Operations LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents