Number of Pairs of Strings With Concatenation Equal to Target

Number of Pairs of Strings With Concatenation Equal to Target - Problem

Given an array of digit strings nums and a digit string target, return the number of pairs of indices (i, j) (where i != j) such that the concatenation of nums[i] + nums[j] equals target.

Example: If nums = ["777", "7", "77", "77"] and target = "7777", then nums[0] + nums[1] = "777" + "7" = "7777" forms one valid pair at indices (0, 1).

Note: The order matters - (i, j) and (j, i) are considered different pairs if i != j.

Input & Output

Example 1 — Basic Case

$ Input: nums = ["777","7","77","77"], target = "7777"

› Output: 2

💡 Note: nums[0] + nums[1] = "777" + "7" = "7777" and nums[1] + nums[0] = "7" + "777" = "7777", so we have 2 valid pairs: (0,1) and (1,0)

Example 2 — Multiple Matches

$ Input: nums = ["123","4","12","34"], target = "1234"

› Output: 2

💡 Note: nums[0] + nums[1] = "123" + "4" = "1234" and nums[2] + nums[3] = "12" + "34" = "1234", giving us pairs (0,1) and (2,3)

Example 3 — No Valid Pairs

$ Input: nums = ["1","1","1"], target = "11"

› Output: 6

💡 Note: All pairs work: (0,1), (0,2), (1,0), (1,2), (2,0), (2,1) all form "1" + "1" = "11"

Constraints

2 ≤ nums.length ≤ 100
1 ≤ nums[i].length ≤ 100
2 ≤ target.length ≤ 100
nums[i] and target consist of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

Array of digit strings and target string

Process

Find all pairs (i,j) where i≠j and nums[i]+nums[j]=target

Output

Count of valid pairs

Key Takeaway

🎯 Key Insight: Use frequency counting and prefix/suffix matching to avoid checking every pair combination

Asked in

M Meta 25 G Google 20 A Amazon 15

The key insight is to avoid checking every pair by using a frequency map. For each string, check if it can be a prefix or suffix of the target, then look up the matching complement in O(1) time. Hash map approach achieves O(n×m) time and O(n) space, much better than O(n²×m) brute force.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n² × m)	O(1)	Try every possible pair (i,j) and check if concatenation equals target
Hash Map Optimization	O(n × m)	O(n)	Use hash map to count strings and find matching prefixes/suffixes efficiently

Brute Force - Check All Pairs — Algorithm Steps

Step 1: Use nested loops to generate all pairs (i,j) where i != j
Step 2: For each pair, concatenate nums[i] + nums[j]
Step 3: Compare with target and increment counter if they match

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Pairs

Create all combinations (i,j) where i ≠ j

Concatenate

Join nums[i] + nums[j] for each pair

Count Matches

Increment counter when concatenation equals target

Code -

solution.c — C

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

int solution(char nums[][101], int numsSize, char* target) {
    int count = 0;
    char concat[201];
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < numsSize; j++) {
            if (i != j) {
                strcpy(concat, nums[i]);
                strcat(concat, nums[j]);
                if (strcmp(concat, target) == 0) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[1001];
    fgets(line, sizeof(line), stdin);
    
    char nums[1000][101];
    int numsSize = 0;
    
    // Simple parsing for array format
    char* ptr = line;
    while (*ptr && numsSize < 1000) {
        if (*ptr == '"') {
            ptr++;
            int len = 0;
            while (*ptr && *ptr != '"' && len < 100) {
                nums[numsSize][len++] = *ptr++;
            }
            nums[numsSize][len] = '\0';
            numsSize++;
            if (*ptr == '"') ptr++;
        }
        ptr++;
    }
    
    char target[101];
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    int result = solution(nums, numsSize, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

Nested loops iterate n×n times, string concatenation and comparison takes O(m) time where m is target length

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables and counter

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 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 - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler