1754. Largest Merge Of Two Strings Medium

1/**
2 * [1754] Largest Merge Of Two Strings
3 *
4 * You are given two strings word1 and word2. You want to construct a string merge in the following way: while either word1 or word2 are non-empty, choose one of the following options:
5 * 
6 * 	If word1 is non-empty, append the first character in word1 to merge and delete it from word1.
7 * 	
8 * 		For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".
9 * 	
10 * 	
11 * 	If word2 is non-empty, append the first character in word2 to merge and delete it from word2.
12 * 	
13 * 		For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".
14 * 	
15 * 	
16 * 
17 * Return the lexicographically largest merge you can construct.
18 * A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b. For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.
19 *  
20 * Example 1:
21 * 
22 * Input: word1 = "cabaa", word2 = "bcaaa"
23 * Output: "cbcabaaaaa"
24 * Explanation: One way to get the lexicographically largest merge is:
25 * - Take from word1: merge = "c", word1 = "abaa", word2 = "bcaaa"
26 * - Take from word2: merge = "cb", word1 = "abaa", word2 = "caaa"
27 * - Take from word2: merge = "cbc", word1 = "abaa", word2 = "aaa"
28 * - Take from word1: merge = "cbca", word1 = "baa", word2 = "aaa"
29 * - Take from word1: merge = "cbcab", word1 = "aa", word2 = "aaa"
30 * - Append the remaining 5 a's from word1 and word2 at the end of merge.
31 * 
32 * Example 2:
33 * 
34 * Input: word1 = "abcabc", word2 = "abdcaba"
35 * Output: "abdcabcabcaba"
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	1 <= word1.length, word2.length <= 3000
41 * 	word1 and word2 consist only of lowercase English letters.
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/largest-merge-of-two-strings/
47// discuss: https://leetcode.com/problems/largest-merge-of-two-strings/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn largest_merge(word1: String, word2: String) -> String {
53        String::new()
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_1754() {
65    }
66}
67