Lexicographically Smallest String After Applying Operations solution and explanation

from collections import deque

def find_lex_smallest_string(s, a, b):
    def add_to_odd_indices(s, a):
        result = list(s)
        for i in range(1, len(s), 2):
            result[i] = str((int(result[i]) + a) % 10)
        return ''.join(result)
    
    def rotate_right(s, b):
        return s[-b:] + s[:-b]

    visited = set()
    queue = deque([s])
    smallest = s

    while queue:
        current = queue.popleft()
        if current < smallest:
            smallest = current
        
        added = add_to_odd_indices(current, a)
        rotated = rotate_right(current, b)

        for new_s in [added, rotated]:
            if new_s not in visited:
                visited.add(new_s)
                queue.append(new_s)

    return smallest

s = "5525"
a = 9
b = 2
print(find_lex_smallest_string(s, a, b))  # Output: "2050"

import java.util.*;

public class Solution {
    private static String addToOddIndices(String s, int a) {
        char[] result = s.toCharArray();
        for (int i = 1; i < s.length(); i += 2) {
            result[i] = (char) (((result[i] - '0' + a) % 10) + '0');
        }
        return new String(result);
    }

    private static String rotateRight(String s, int b) {
        int n = s.length();
        return s.substring(n - b) + s.substring(0, n - b);
    }

    public static String findLexSmallestString(String s, int a, int b) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        String smallest = s;
        queue.offer(s);
        visited.add(s);

        while (!queue.isEmpty()) {
            String current = queue.poll();
            if (current.compareTo(smallest) < 0) smallest = current;

            String added = addToOddIndices(current, a);
            if (!visited.contains(added)) {
                visited.add(added);
                queue.offer(added);
            }

            String rotated = rotateRight(current, b);
            if (!visited.contains(rotated)) {
                visited.add(rotated);
                queue.offer(rotated);
            }
        }
        return smallest;
    }

    public static void main(String[] args) {
        System.out.println(findLexSmallestString("5525", 9, 2)); // Output: "2050"
    }
}

#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>

using namespace std;

string addToOddIndices(const string& s, int a) {
    string result = s;
    for (int i = 1; i < s.size(); i += 2) {
        result[i] = '0' + (result[i] - '0' + a) % 10;
    }
    return result;
}

string rotateRight(const string& s, int b) {
    int n = s.size();
    return s.substr(n - b) + s.substr(0, n - b);
}

string findLexSmallestString(string s, int a, int b) {
    unordered_set<string> visited;
    queue<string> q;
    string smallest = s;
    q.push(s);
    visited.insert(s);

    while (!q.empty()) {
        string current = q.front(); q.pop();
        if (current < smallest) smallest = current;

        // Add to odd indices
        string added = addToOddIndices(current, a);
        if (visited.find(added) == visited.end()) {
            visited.insert(added);
            q.push(added);
        }

        // Rotate right by b
        string rotated = rotateRight(current, b);
        if (visited.find(rotated) == visited.end()) {
            visited.insert(rotated);
            q.push(rotated);
        }
    }
    return smallest;
}

int main() {
    cout << findLexSmallestString("5525", 9, 2) << endl; // Output: "2050"
    return 0;
}

function addToOddIndices(s, a) {
    let result = s.split("");
    for (let i = 1; i < s.length; i += 2) {
        result[i] = ((parseInt(result[i]) + a) % 10).toString();
    }
    return result.join("");
}

function rotateRight(s, b) {
    return s.slice(-b) + s.slice(0, -b);
}

function findLexSmallestString(s, a, b) {
    let visited = new Set();
    let queue = [s];
    let smallest = s;
    
    while (queue.length) {
        let current = queue.shift();
        if (current < smallest) smallest = current;
        
        let added = addToOddIndices(current, a);
        let rotated = rotateRight(current, b);
        
        if (!visited.has(added)) {
            visited.add(added);
            queue.push(added);
        }
        
        if (!visited.has(rotated)) {
            visited.add(rotated);
            queue.push(rotated);
        }
    }
    return smallest;
}

console.log(findLexSmallestString("5525", 9, 2)); // Output: "2050";

using System;
using System.Collections.Generic;

public class Solution {
    private static string AddToOddIndices(string s, int a) {
        char[] result = s.ToCharArray();
        for (int i = 1; i < s.Length; i += 2) {
            result[i] = (char)(((result[i] - '0' + a) % 10) + '0');
        }
        return new string(result);
    }

    private static string RotateRight(string s, int b) {
        int n = s.Length;
        return s.Substring(n - b) + s.Substring(0, n - b);
    }

    public static string FindLexSmallestString(string s, int a, int b) {
        HashSet<string> visited = new HashSet<string>();
        Queue<string> queue = new Queue<string>();
        string smallest = s;
        queue.Enqueue(s);
        visited.Add(s);

        while (queue.Count > 0) {
            string current = queue.Dequeue();
            if (string.Compare(current, smallest) < 0) smallest = current;

            string added = AddToOddIndices(current, a);
            if (!visited.Contains(added)) {
                visited.Add(added);
                queue.Enqueue(added);
            }

            string rotated = RotateRight(current, b);
            if (!visited.Contains(rotated)) {
                visited.Add(rotated);
                queue.Enqueue(rotated);
            }
        }
        return smallest;
    }

    public static void Main() {
        Console.WriteLine(FindLexSmallestString("5525", 9, 2)); // Output: "2050"
    }
}

def find_lex_smallest_string_math(s, a, b):
    from itertools import combinations
    def add_to_odd_indices(s, a):
        return ''.join((chr((ord(c) - ord('0') + (a if i % 2 else 0)) % 10 + ord('0')) if i % 2 else c) for i, c in enumerate(s))

    def get_rotations(s, b):
        n = len(s)
        rotations = [s]
        for i in range(n):
            s = s[-b:] + s[:-b]
            rotations.append(s)
        return rotations

    smallest = s
    visited = set()

    for add_count in range(10):
        modified = s
        for _ in range(add_count):
            modified = add_to_odd_indices(modified, a)

        for rotation in get_rotations(modified, b):
            if rotation not in visited and rotation < smallest:
                smallest = rotation
            visited.add(rotation)

    return smallest

s = "5525"
a = 9
b = 2
print(find_lex_smallest_string_math(s, a, b))  # Output: "2050"

function findLexSmallestString(s: string, a: number, b: number): string {
    const q: string[] = [s];
    const vis = new Set<string>([s]);
    let ans = s;
    let i = 0;
    while (i < q.length) {
        s = q[i++];
        if (ans > s) {
            ans = s;
        }
        const t1 = s
            .split('')
            .map((c, j) => (j & 1 ? String((Number(c) + a) % 10) : c))
            .join('');
        const t2 = s.slice(-b) + s.slice(0, -b);
        for (const t of [t1, t2]) {
            if (!vis.has(t)) {
                vis.add(t);
                q.push(t);
            }
        }
    }
    return ans;
}

func findLexSmallestString(s string, a int, b int) string {
	q := []string{s}
	vis := map[string]bool{s: true}
	ans := s
	n := len(s)
	for len(q) > 0 {
		s = q[0]
		q = q[1:]
		if ans > s {
			ans = s
		}
		t1 := []byte(s)
		for i := 1; i < n; i += 2 {
			t1[i] = byte((int(t1[i]-'0')+a)%10 + '0')
		}
		t2 := s[n-b:] + s[:n-b]
		for _, t := range []string{string(t1), t2} {
			if !vis[t] {
				vis[t] = true
				q = append(q, t)
			}
		}
	}
	return ans
}

function findLexSmallestString(s: string, a: number, b: number): string {
    let ans = s;
    const n = s.length;
    let arr = s.split('');
    for (let _ = 0; _ < n; _++) {
        arr = arr.slice(-b).concat(arr.slice(0, -b));
        for (let j = 0; j < 10; j++) {
            for (let k = 1; k < n; k += 2) {
                arr[k] = String((Number(arr[k]) + a) % 10);
            }
            if (b & 1) {
                for (let p = 0; p < 10; p++) {
                    for (let k = 0; k < n; k += 2) {
                        arr[k] = String((Number(arr[k]) + a) % 10);
                    }
                    const t = arr.join('');
                    if (ans > t) {
                        ans = t;
                    }
                }
            } else {
                const t = arr.join('');
                if (ans > t) {
                    ans = t;
                }
            }
        }
    }
    return ans;
}

func findLexSmallestString(s string, a int, b int) string {
	n := len(s)
	ans := s
	for _ = range s {
		s = s[n-b:] + s[:n-b]
		cs := []byte(s)
		for j := 0; j < 10; j++ {
			for k := 1; k < n; k += 2 {
				cs[k] = byte((int(cs[k]-'0')+a)%10 + '0')
			}
			if b&1 == 1 {
				for p := 0; p < 10; p++ {
					for k := 0; k < n; k += 2 {
						cs[k] = byte((int(cs[k]-'0')+a)%10 + '0')
					}
					s = string(cs)
					if ans > s {
						ans = s
					}
				}
			} else {
				s = string(cs)
				if ans > s {
					ans = s
				}
			}
		}
	}
	return ans
}