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

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

✓ Brute Force - Check All Pairs

⏱️ Time: O(n² × m) Space: O(1)

Iterate through all pairs of indices (i,j) where i != j, concatenate nums[i] + nums[j], and count how many equal the target string.

Hash Map Optimization

⏱️ Time: O(n × m) Space: O(n)

For each string in nums, try all possible ways to split the target string. If the string matches a prefix, look for the suffix in a frequency map. This avoids checking every pair explicitly.

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;
}

void parseJsonArray(const char* str, char nums[][101], int* size) {
    *size = 0;
    const char* ptr = str;
    
    while (*ptr && *ptr != '[') ptr++;
    if (*ptr == '[') ptr++;
    
    while (*ptr && *ptr != ']') {
        while (*ptr == ' ' || *ptr == ',' || *ptr == '\n' || *ptr == '\t') ptr++;
        if (*ptr == ']' || *ptr == '\0') break;
        
        if (*ptr == '"') {
            ptr++;
            int len = 0;
            while (*ptr && *ptr != '"' && len < 100) {
                nums[*size][len++] = *ptr++;
            }
            nums[*size][len] = '\0';
            (*size)++;
            if (*ptr == '"') ptr++;
        } else {
            ptr++;
        }
    }
}

int main() {
    char line[1001];
    fgets(line, sizeof(line), stdin);
    
    char nums[1000][101];
    int numsSize = 0;
    
    parseJsonArray(line, nums, &numsSize);
    
    char targetLine[101];
    fgets(targetLine, sizeof(targetLine), stdin);
    
    // Remove newline from target
    char* newline = strchr(targetLine, '\n');
    if (newline) *newline = '\0';
    
    int result = solution(nums, numsSize, targetLine);  // Target is plain string
    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

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables and counter

⚡ Linearithmic 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler