leetcode

commit 293c6cb70524a1cbc7c8947c2c6e24db02bbd4c4
parent 1f00ecabf08fcb91339dde49c06c5295703b66c2
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 18 Oct 2025 19:18:32 -0600

1625. lexicographically smallest string after applying operations

Diffstat:
A
lex_smallest_str_op.c
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
lex_smallest_str_op.py
 | 
47
+++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 102 insertions(+), 0 deletions(-)
diff --git a/lex_smallest_str_op.c b/lex_smallest_str_op.c
@@ -0,0 +1,55 @@
+// 1625. Lexicographically Smallest String After Applying Operations
+#include "leetcode.h"
+
+/*
+ * 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 in any order on 's': add 'a' to all odd
+ * indices of 's', or rotate 's' to the right by 'b' positions. return the
+ * lexicographically smallest string you can obtain by applying the above
+ * operations. a string 'a' is lexicographically smaller than a string 'b' 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'.
+ */
+
+char *findLexSmallestString(char *s, int a, int b) {
+  int n = strlen(s);
+  bool *vis = (bool *)calloc(n, sizeof(int));
+  char *ans = (char *)calloc(n + 1, sizeof(char));
+  strcpy(ans, s);
+  char *str = (char *)malloc((2 * n + 1) * sizeof(char));
+  sprintf(str, "%s%s", s, s);
+  for (int i = 0; !vis[i]; i = (i + b) % n) {
+    vis[i] = true;
+    for (int j = 0; j < 10; j++) {
+      int lim = !(b % 2) ? 0 : 9;
+      for (int k = 0; k <= lim; k++) {
+        char *tmp = (char *)malloc((n + 1) * sizeof(char));
+        strncpy(tmp, str + i, n);
+        tmp[n] = '\0';
+        for (int p = 1; p < n; p += 2)
+          tmp[p] = '0' + (tmp[p] - '0' + j * a) % 10;
+        for (int p = 0; p < n; p += 2)
+          tmp[p] = '0' + (tmp[p] - '0' + k * a) % 10;
+        if (strcmp(tmp, ans) < 0)
+          strcpy(ans, tmp);
+        free(tmp);
+      }
+    }
+  }
+  free(vis);
+  free(str);
+  return ans;
+}
+
+int main() {
+  char *s1 = "5525", *flss1 = findLexSmallestString(s1, 9, 2);
+  char *str = "74", *flss2 = findLexSmallestString(str, 5, 1);
+  char *s3 = "0011", *flss3 = findLexSmallestString(s3, 4, 2);
+  printf("%s\n", flss1); // expect: 2050
+  printf("%s\n", flss2); // expect: 24
+  printf("%s\n", flss3); // expect:  0011
+  free(flss1);
+  free(flss2);
+  free(flss3);
+}
diff --git a/lex_smallest_str_op.py b/lex_smallest_str_op.py
@@ -0,0 +1,47 @@
+# 1625. 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 in any order on 's': add 'a' to all odd
+indices of 's', or rotate 's' to the right by 'b' positions. return the
+lexicographically smallest string you can obtain by applying the above
+operations. a string 'a' is lexicographically smaller than a string 'b' 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'.
+"""
+
+
+class Solution(object):
+    def findLexSmallestString(self, s, a, b):
+        """
+        :type s: str
+        :type a: int
+        :type b: int
+        :rtype: str
+        """
+        n, ans = len(s), s
+        vis = [False] * n
+        s, i = s + s, 0
+        while not vis[i]:
+            vis[i] = True
+            for j in range(10):
+                lim = 0 if b % 2 == 0 else 9
+                for k in range(lim + 1):
+                    tmp = list(s[i : i + n])
+                    for p in range(1, n, 2):
+                        tmp[p] = str((int(tmp[p]) + j * a) % 10)
+                    for p in range(0, n, 2):
+                        tmp[p] = str((int(tmp[p]) + k * a) % 10)
+                    tmp_str = "".join(tmp)
+                    if tmp_str < ans:
+                        ans = tmp_str
+            i = (i + b) % n
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.findLexSmallestString(s="5525", a=9, b=2))
+    print(obj.findLexSmallestString(s="74", a=5, b=1))
+    print(obj.findLexSmallestString(s="0011", a=4, b=2))