diff options
-rw-r--r-- | using_robot_print_lex_small_str.c | 67 | ||||
-rw-r--r-- | using_robot_print_lex_small_str.py | 35 |
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")) |