aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-05 18:44:21 -0600
committerJack Sangdahl <[email protected]>2025-06-05 18:44:21 -0600
commit79c7e9462c5cb51657167f9412b5c3711a5d8a61 (patch)
treecbdd0787d3518d390c497a6d8e1e1117ed14af10
parenta05784326180667fd695dd35d97dce314ab0a31c (diff)
downloadleetcode-79c7e9462c5cb51657167f9412b5c3711a5d8a61.tar.gz
leetcode-79c7e9462c5cb51657167f9412b5c3711a5d8a61.zip
2434. using a robot to print the lexicographically smallest string
-rw-r--r--using_robot_print_lex_small_str.c67
-rw-r--r--using_robot_print_lex_small_str.py35
2 files changed, 102 insertions, 0 deletions
diff --git a/using_robot_print_lex_small_str.c b/using_robot_print_lex_small_str.c
new file mode 100644
index 0000000..888b97b
--- /dev/null
+++ b/using_robot_print_lex_small_str.c
@@ -0,0 +1,67 @@
+// 2434. Using a Robot to Print the Lexicographically Smallest String
+#include "leetcode.h"
+
+/*
+ * you are given a string 's' and a robot that currently holds an empty string
+ * 't'. apply one of the followiing operations until 's' and 't' are both empty.
+ * remove the first character of a string 's' and give it to the robot. the
+ * robot will append this charcter to the string 't'. remove the last character
+ * of a string 't' and give it to the robot. the robot will write this character
+ * on paper.
+ */
+
+char *robotWithString(char *s) {
+ int n = strlen(s), a_idx = 0, t_idx = 0, min_idx = 0, begin = 0;
+ char *ans = (char *)malloc((n + 1) * sizeof(char));
+ ans[n] = '\0';
+ char *t = (char *)malloc(n * sizeof(char)), low = 'a';
+ while (begin < n) {
+ char min = s[begin];
+ min_idx = begin;
+ for (int i = begin; i < n; i++) {
+ if (s[i] == low) {
+ min_idx = i;
+ min = low;
+ break;
+ } else if (s[i] < min) {
+ min = s[i];
+ min_idx = i;
+ }
+ }
+ low = s[min_idx];
+ if (!t_idx) {
+ ans[a_idx++] = low;
+ for (int j = begin; j < min_idx; j++)
+ t[t_idx++] = s[j];
+ } else {
+ while (t_idx >= 0) {
+ if (t_idx > 0 && t[t_idx - 1] <= s[min_idx])
+ ans[a_idx++] = t[t_idx-- - 1];
+ else {
+ ans[a_idx++] = s[min_idx];
+ for (int j = begin; j < min_idx; j++)
+ t[t_idx++] = s[j];
+ break;
+ }
+ }
+ }
+ begin = min_idx + 1;
+ }
+ for (int i = t_idx - 1; i >= 0; i--)
+ ans[a_idx++] = t[i];
+ free(t);
+ return ans;
+}
+
+int main() {
+ char *s1 = "zza", *s2 = "bac", *s3 = "bdda";
+ char *rws1 = robotWithString(s1);
+ char *rws2 = robotWithString(s2);
+ char *rws3 = robotWithString(s3);
+ printf("%s\n", rws1); // expect: azz
+ printf("%s\n", rws2); // expect: abc
+ printf("%s\n", rws3); // expect: addb
+ free(rws1);
+ free(rws2);
+ free(rws3);
+}
diff --git a/using_robot_print_lex_small_str.py b/using_robot_print_lex_small_str.py
new file mode 100644
index 0000000..3189464
--- /dev/null
+++ b/using_robot_print_lex_small_str.py
@@ -0,0 +1,35 @@
+# 2434. Using a Robot to Print the Lexicographically Smallest String
+from collections import Counter
+
+"""
+you are given a string 's' and a robot that currently holds an empty string
+'t'. apply one of the followiing operations until 's' and 't' are both empty.
+remove the first character of a string 's' and give it to the robot. the
+robot will append this charcter to the string 't'. remove the last character
+of a string 't' and give it to the robot. the robot will write this character
+on paper.
+"""
+
+
+class Solution(object):
+ def robotWithString(self, s):
+ """
+ :type s: str
+ :rtype: str
+ """
+ cnt, low, ans, t = Counter(s), "a", [], []
+ for i in s:
+ t += i
+ cnt[i] -= 1
+ while low < "z" and cnt[low] == 0:
+ low = chr(ord(low) + 1)
+ while t and t[-1] <= low:
+ ans += t.pop()
+ return "".join(ans)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.robotWithString(s="zza"))
+ print(obj.robotWithString(s="bac"))
+ print(obj.robotWithString(s="bdda"))