diff options
-rw-r--r-- | find_lex_large_str_box1.c | 40 | ||||
-rw-r--r-- | find_lex_large_str_box1.py | 30 |
2 files changed, 70 insertions, 0 deletions
diff --git a/find_lex_large_str_box1.c b/find_lex_large_str_box1.c new file mode 100644 index 0000000..8cc8df1 --- /dev/null +++ b/find_lex_large_str_box1.c @@ -0,0 +1,40 @@ +// 3403. Find the Lexicographically Largest String From the Box I +#include "leetcode.h" + +/* + * you are given a string 'word', and an integer 'numFriends'. alice is + * organising a game for her 'numFriends' friends. there are multiple rounds in + * the game, where each round: 'word' is split into 'numFriends' non-empty + * strings such that no previous round has the exact same split, and all the + * split words are put into a box. find the lexicographically largest string + * from the box after all rounds are finished. + */ + +char *answerString(char *word, int numFriends) { + int n = strlen(word), m = n - (numFriends - 1); + if (numFriends == 1) { + char *ans = (char *)malloc((n + 1) * sizeof(char)); + strcpy(ans, word); + return ans; + } + char *ans = (char *)malloc((m + 1) * sizeof(char)); + ans[0] = '\0'; + for (int i = 0; i < m; ++i) { + int k = n - i < m ? n - i : m; + char *tmp = (char *)malloc((k + 1) * sizeof(char)); + strncpy(tmp, word + i, k); + tmp[k] = '\0'; + if (strcmp(ans, tmp) < 0) { + free(ans); + ans = tmp; + } else + free(tmp); + } + return ans; +} + +int main() { + char *w1 = "dbca", *w2 = "gggg"; + printf("%s\n", answerString(w1, 2)); // expect: dbc + printf("%s\n", answerString(w2, 4)); // expect: g +} diff --git a/find_lex_large_str_box1.py b/find_lex_large_str_box1.py new file mode 100644 index 0000000..1b29d1f --- /dev/null +++ b/find_lex_large_str_box1.py @@ -0,0 +1,30 @@ +# 3403. Find the Lexicographically Largest String From the Box I + +""" +you are given a string 'word', and an integer 'numFriends'. alice is +organising a game for her 'numFriends' friends. there are multiple rounds in +the game, where each round: 'word' is split into 'numFriends' non-empty +strings such that no previous round has the exact same split, and all the +split words are put into a box. find the lexicographically largest string +from the box after all rounds are finished. +""" + + +class Solution(object): + def answerString(self, word, numFriends): + """ + :type word: str + :type numFriends: int + :rtype: str + """ + n = len(word) + m = n - numFriends + 1 + if numFriends == 1: + return word + return max(word[i : i + m] for i in range(n)) + + +if __name__ == "__main__": + obj = Solution() + print(obj.answerString(word="dbca", numFriends=2)) + print(obj.answerString(word="gggg", numFriends=4)) |