Largest Merge Of Two Strings - Practice Coding Problems

Largest Merge Of Two Strings - Problem

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.
If word2 is non-empty, append the first character in word2 to merge and delete it from word2.

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.

Input & Output

Example 1 — Basic Case

$ Input: word1 = "cab", word2 = "ab"

› Output: "cabab"

💡 Note: At each step: "cab" vs "ab" → choose 'c', then "ab" vs "ab" → choose 'a', then "b" vs "b" → choose 'a', append remaining "bb"

Example 2 — Equal Start

$ Input: word1 = "abcabc", word2 = "abdaba"

› Output: "abdabacabcabc"

💡 Note: "abcabc" vs "abdaba" → "abdaba" is larger, so choose 'a' from word2. Continue comparing suffixes.

Example 3 — One Empty

$ Input: word1 = "a", word2 = "b"

› Output: "ba"

💡 Note: "a" vs "b" → 'b' > 'a', so choose 'b' first, then append remaining 'a'

Constraints

1 ≤ word1.length, word2.length ≤ 3000
word1 and word2 consist only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings word1="cab" and word2="ab"

Process

At each step, compare remaining suffixes and choose optimally

Output

Lexicographically largest merge "cabab"

Key Takeaway

🎯 Key Insight: Always choose from the string with the lexicographically larger remaining suffix

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is to use a greedy approach: at each step, choose the character from the string whose remaining suffix is lexicographically larger. This ensures we always make the optimal choice for the largest possible merge. Best approach is greedy suffix comparison. Time: O((m+n)²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2^(m+n))	O(m+n)	Try all possible ways to merge the strings and return the lexicographically largest
Greedy Choice	O((m+n)²)	O(1)	At each step, choose the character that leads to lexicographically larger result

Brute Force Recursion — Algorithm Steps

At each step, try taking from word1 and word2
Recursively solve for remaining strings
Return the lexicographically larger result

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with both strings at index 0

Branch

Try taking from word1 and word2 separately

Compare

Return lexicographically larger result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* merge(const char* word1, const char* word2, int i, int j, int len1, int len2) {
    if (i >= len1) {
        char* result = malloc(len2 - j + 1);
        strcpy(result, word2 + j);
        return result;
    }
    if (j >= len2) {
        char* result = malloc(len1 - i + 1);
        strcpy(result, word1 + i);
        return result;
    }
    
    // Try taking from word1
    char* choice1_rest = merge(word1, word2, i + 1, j, len1, len2);
    char* choice1 = malloc(strlen(choice1_rest) + 2);
    choice1[0] = word1[i];
    strcpy(choice1 + 1, choice1_rest);
    
    // Try taking from word2
    char* choice2_rest = merge(word1, word2, i, j + 1, len1, len2);
    char* choice2 = malloc(strlen(choice2_rest) + 2);
    choice2[0] = word2[j];
    strcpy(choice2 + 1, choice2_rest);
    
    // Return lexicographically larger
    char* result;
    if (strcmp(choice1, choice2) > 0) {
        result = choice1;
        free(choice2);
    } else {
        result = choice2;
        free(choice1);
    }
    free(choice1_rest);
    free(choice2_rest);
    return result;
}

char* solution(const char* word1, const char* word2) {
    return merge(word1, word2, 0, 0, strlen(word1), strlen(word2));
}

int main() {
    char word1[1001], word2[1001];
    fgets(word1, sizeof(word1), stdin);
    fgets(word2, sizeof(word2), stdin);
    word1[strcspn(word1, "\n")] = 0;
    word2[strcspn(word2, "\n")] = 0;
    char* result = solution(word1, word2);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^(m+n))

At each step we have 2 choices, with m+n total steps

✓ Linear Growth

Space Complexity

O(m+n)

Recursion depth equals sum of string lengths

⚡ Linearithmic Space

32.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler