diff options
-rw-r--r-- | res_str_adj_remove.c | 42 | ||||
-rw-r--r-- | res_str_adj_remove.py | 38 |
2 files changed, 80 insertions, 0 deletions
diff --git a/res_str_adj_remove.c b/res_str_adj_remove.c new file mode 100644 index 0000000..c2792f0 --- /dev/null +++ b/res_str_adj_remove.c @@ -0,0 +1,42 @@ +// 3561. Resulting String After Adjacent Removals +#include "leetcode.h" + +/* + * you are given a string 's' consisting of lowercase english letters. you must + * repeatedly perform the following operation while the string 's' has at least + * two consecutive characters: remove the leftmost pair of adjacent characters + * in the string that are consecutive in the alphabet, in either order, and + * shift the remaining characters to the left to fill the gap. return the + * resulting string after no more operations can be performed. note: consider + * the alphabet as circular, thus 'a' and 'z' are consecutive. + */ + +bool helper(char a, char b) { + int c = fabs(a - b); + return c == 1 || c == 25; +} + +char *resultingString(char *s) { + int n = strlen(s), top = -1; + char *ans = (char *)malloc((n + 1) * sizeof(char)); + for (int i = 0; i < n; i++) { + if (top >= 0 && helper(ans[top], s[i])) + top--; + else + ans[++top] = s[i]; + } + ans[top + 1] = '\0'; + return ans; +} + +int main() { + char *s1 = "abc", *rs1 = resultingString(s1); + char *s2 = "adcb", *rs2 = resultingString(s2); + char *s3 = "zadb", *rs3 = resultingString(s3); + printf("%s\n", rs1); // expect: c + printf("%s\n", rs2); // expect: null + printf("%s\n", rs3); // expect: db + free(rs1); + free(rs2); + free(rs3); +} diff --git a/res_str_adj_remove.py b/res_str_adj_remove.py new file mode 100644 index 0000000..2949e18 --- /dev/null +++ b/res_str_adj_remove.py @@ -0,0 +1,38 @@ +# 3561. Resulting String After Adjacent Removals + +""" +you are given a string 's' consisting of lowercase english letters. you must +repeatedly perform the following operation while the string 's' has at least +two consecutive characters: remove the leftmost pair of adjacent characters +in the string that are consecutive in the alphabet, in either order, and +shift the remaining characters to the left to fill the gap. return the +resulting string after no more operations can be performed. note: consider +the alphabet as circular, thus 'a' and 'z' are consecutive. +""" + + +class Solution(object): + def resultingString(self, s): + """ + :type s: str + :rtype: str + """ + ans = [] + + def helper(a): + c = abs(ord(ans[-1]) - ord(a)) + return c == 1 or c == 25 + + for i in s: + if ans and helper(i): + ans.pop() + else: + ans.append(i) + return "".join(ans) + + +if __name__ == "__main__": + obj = Solution() + print(obj.resultingString(s="abc")) + print(obj.resultingString(s="adcb")) + print(obj.resultingString(s="zadb")) |