Lexicographically Smallest String After Applying Operations

medium string brute force enumeration

Problem

You are given a string s of even length made of digits 0–9, and two integers a and b. You may apply two operations any number of times, in any order: add a to every odd index (digits wrap past 9 back to 0), or rotate s right by b positions. Return the lexicographically smallest string you can obtain.

Inputs = "5525", a = 9, b = 2

Output"2050"

Rotating and adding repeatedly can reach "2050"; nothing smaller is reachable.

Inputs = "74", a = 5, b = 1

Output"24"

With b odd, a rotation can move even digits to odd slots, so both positions are adjustable.

s (digits, even length)

a (1–9)

b (1 … len-1)

def smallest_string(s, a, b):
    n = len(s)
    best = s
    seen = set()
    rot = s
    while rot not in seen:
        seen.add(rot)
        for k1 in range(10):
            t = list(rot)
            for i in range(1, n, 2):
                t[i] = str((int(t[i]) + k1 * a) % 10)
            if b % 2 == 1:
                for k2 in range(10):
                    u = t[:]
                    for i in range(0, n, 2):
                        u[i] = str((int(u[i]) + k2 * a) % 10)
                    best = min(best, "".join(u))
            else:
                best = min(best, "".join(t))
        rot = rot[-b:] + rot[:-b]
    return best

function smallestString(s, a, b) {
  const n = s.length;
  let best = s;
  const seen = new Set();
  let rot = s;
  while (!seen.has(rot)) {
    seen.add(rot);
    for (let k1 = 0; k1 < 10; k1++) {
      const t = rot.split("");
      for (let i = 1; i < n; i += 2)
        t[i] = String((+t[i] + k1 * a) % 10);
      if (b % 2 === 1) {
        for (let k2 = 0; k2 < 10; k2++) {
          const u = t.slice();
          for (let i = 0; i < n; i += 2)
            u[i] = String((+u[i] + k2 * a) % 10);
          if (u.join("") < best) best = u.join("");
        }
      } else if (t.join("") < best) best = t.join("");
    }
    rot = rot.slice(n - b) + rot.slice(0, n - b);
  }
  return best;
}

String smallestString(String s, int a, int b) {
    int n = s.length();
    String best = s, rot = s;
    Set<String> seen = new HashSet<>();
    while (!seen.contains(rot)) {
        seen.add(rot);
        for (int k1 = 0; k1 < 10; k1++) {
            char[] t = rot.toCharArray();
            for (int i = 1; i < n; i += 2)
                t[i] = (char) ('0' + (t[i] - '0' + k1 * a) % 10);
            if (b % 2 == 1)
                for (int k2 = 0; k2 < 10; k2++) {
                    char[] u = t.clone();
                    for (int i = 0; i < n; i += 2)
                        u[i] = (char) ('0' + (u[i] - '0' + k2 * a) % 10);
                    String c = new String(u);
                    if (c.compareTo(best) < 0) best = c;
                }
            else {
                String c = new String(t);
                if (c.compareTo(best) < 0) best = c;
            }
        }
        rot = rot.substring(n - b) + rot.substring(0, n - b);
    }
    return best;
}

string smallestString(string s, int a, int b) {
    int n = s.size();
    string best = s, rot = s;
    set<string> seen;
    while (!seen.count(rot)) {
        seen.insert(rot);
        for (int k1 = 0; k1 < 10; k1++) {
            string t = rot;
            for (int i = 1; i < n; i += 2)
                t[i] = '0' + (t[i] - '0' + k1 * a) % 10;
            if (b % 2 == 1)
                for (int k2 = 0; k2 < 10; k2++) {
                    string u = t;
                    for (int i = 0; i < n; i += 2)
                        u[i] = '0' + (u[i] - '0' + k2 * a) % 10;
                    best = min(best, u);
                }
            else
                best = min(best, t);
        }
        rot = rot.substr(n - b) + rot.substr(0, n - b);
    }
    return best;
}

Explanation

Each operation is reversible and can be repeated, so the reachable strings form a finite set we can simply enumerate. The trick is to see how few independent choices there really are.

Rotations. Rotating right by b over and over visits a cycle of distinct rotations. We follow that cycle with a seen set and stop once a rotation repeats — there are at most n / gcd(n, b) of them.

Adding to odd indices. The add operation always bumps every odd index by the same amount, so after k1 applications each odd digit becomes (d + k1·a) mod 10. Only k1 = 0…9 can ever produce distinct results, so we try all ten.

When b is odd. A rotation by an odd b shifts even positions into odd positions and vice-versa, which means the even digits become adjustable too. In that case we additionally try every shift k2 = 0…9 on the even indices.

For each rotation we form every candidate string and keep the lexicographic minimum in best. The whole search is tiny: at most n rotations × 10 (× 10) candidates.

Time: O(n² · 10 · [b odd ? 10]) Space: O(n²)