Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1754.html

1754. Largest Merge Of Two Strings

Level

Medium

Description

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:

  • If word1 is non-empty, append the first character in word1 to merge and delete it from word1.
    • For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".
  • If word2 is non-empty, append the first character in word2 to merge and delete it from word2.
    • For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".

Return the lexicographically largest merge you can construct.

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.

Example 1:

Input: word1 = “cabaa”, word2 = “bcaaa”

Output: “cbcabaaaaa”

Explanation: One way to get the lexicographically largest merge is:

  • Take from word1: merge = “c”, word1 = “abaa”, word2 = “bcaaa”
  • Take from word2: merge = “cb”, word1 = “abaa”, word2 = “caaa”
  • Take from word2: merge = “cbc”, word1 = “abaa”, word2 = “aaa”
  • Take from word1: merge = “cbca”, word1 = “baa”, word2 = “aaa”
  • Take from word1: merge = “cbcab”, word1 = “aa”, word2 = “aaa”
  • Append the remaining 5 a’s from word1 and word2 at the end of merge.

Example 2:

Input: word1 = “abcabc”, word2 = “abdcaba”

Output: “abdcabcabcaba”

Constraints:

  • 1 <= word1.length, word2.length <= 3000
  • word1 and word2 consist only of lowercase English letters.

Solution

Use two pointers index1 and index2 to point to indices of word1 and word2, respectively. Each time compare the two characters at index1 and index2. If the two characters are different, append the larger character to merge. Otherwise, compare the remaining substrings of word1 and word2 starting from index1 and index2 respectively, and select the first character of the greater substring and append it to merge. Finally, return merge.

  • class Solution {
    public String largestMerge(String word1, String word2) {
        StringBuffer merge = new StringBuffer();
        int length1 = word1.length(), length2 = word2.length();
        int index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            char c1 = word1.charAt(index1), c2 = word2.charAt(index2);
            if (c1 > c2) {
                merge.append(c1);
                index1++;
            } else if (c1 < c2) {
                merge.append(c2);
                index2++;
            } else {
                int temp1 = index1 + 1, temp2 = index2 + 1;
                boolean flag = true;
                while (temp1 < length1 && temp2 < length2) {
                    if (word1.charAt(temp1) == word2.charAt(temp2)) {
                        temp1++;
                        temp2++;
                    } else if (word1.charAt(temp1) > word2.charAt(temp2)) {
                        merge.append(c1);
                        index1++;
                        flag = false;
                        break;
                    } else {
                        merge.append(c2);
                        index2++;
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    if (temp2 == length2) {
                        merge.append(c1);
                        index1++;
                    } else {
                        merge.append(c2);
                        index2++;
                    }
                }
            }
        }
        while (index1 < length1) {
            merge.append(word1.charAt(index1));
            index1++;
        }
        while (index2 < length2) {
            merge.append(word2.charAt(index2));
            index2++;
        }
        return merge.toString();
    }
}

############

class Solution {
    public String largestMerge(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int i = 0, j = 0;
        StringBuilder ans = new StringBuilder();
        while (i < m && j < n) {
            boolean gt = word1.substring(i).compareTo(word2.substring(j)) > 0;
            ans.append(gt ? word1.charAt(i++) : word2.charAt(j++));
        }
        ans.append(word1.substring(i));
        ans.append(word2.substring(j));
        return ans.toString();
    }
}

  • // OJ: https://leetcode.com/problems/largest-merge-of-two-strings/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    string largestMerge(string word1, string word2) {
        priority_queue<string> q;
        q.push(word1);
        q.push(word2);
        string ans;
        while (q.size()) {
            auto s = q.top();
            q.pop();
            ans += s[0];
            if (s.size() > 1) q.push(s.substr(1));
        }
        return ans;
    }
};

  • class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        i = j = 0
        ans = []
        while i < len(word1) and j < len(word2):
            if word1[i:] > word2[j:]:
                ans.append(word1[i])
                i += 1
            else:
                ans.append(word2[j])
                j += 1
        ans.append(word1[i:])
        ans.append(word2[j:])
        return "".join(ans)

############

# 1754. Largest Merge Of Two Strings
# https://leetcode.com/problems/largest-merge-of-two-strings

class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        res = ""
        
        while word1 and word2:
            if word1 >= word2:
                res += word1[0]
                word1 = word1[1:]
            else:
                res += word2[0]
                word2 = word2[1:]
        
        res += word1 or word2
        
        return res


  • func largestMerge(word1 string, word2 string) string {
	m, n := len(word1), len(word2)
	i, j := 0, 0
	var ans strings.Builder
	for i < m && j < n {
		if word1[i:] > word2[j:] {
			ans.WriteByte(word1[i])
			i++
		} else {
			ans.WriteByte(word2[j])
			j++
		}
	}
	ans.WriteString(word1[i:])
	ans.WriteString(word2[j:])
	return ans.String()
}

  • function largestMerge(word1: string, word2: string): string {
    const m = word1.length;
    const n = word2.length;
    let ans = '';
    let i = 0;
    let j = 0;
    while (i < m && j < n) {
        ans += word1.slice(i) > word2.slice(j) ? word1[i++] : word2[j++];
    }
    ans += word1.slice(i);
    ans += word2.slice(j);
    return ans;
}


  • impl Solution {
    pub fn largest_merge(word1: String, word2: String) -> String {
        let word1 = word1.as_bytes();
        let word2 = word2.as_bytes();
        let m = word1.len();
        let n = word2.len();
        let mut ans = String::new();
        let mut i = 0;
        let mut j = 0;
        while i < m && j < n {
            if word1[i..] > word2[j..] {
                ans.push(word1[i] as char);
                i += 1;
            } else {
                ans.push(word2[j] as char);
                j += 1;
            }
        }
        word1[i..].iter().for_each(|c| ans.push(*c as char));
        word2[j..].iter().for_each(|c| ans.push(*c as char));
        ans
    }
}

All Problems

All Solutions