Number of Pairs of Strings With Concatenation Equal to Target

Medium
1228.

Number of Pairs of Strings With Concatenation Equal to Target

Number of Pairs of Strings With Concatenation Equal to Target is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

You are given an array nums of digit strings and a digit string target.

Count the pairs of indices (i, j) with i != j such that the concatenation nums[i] + nums[j] equals target. Pairs are ordered: (i, j) and (j, i) are different pairs and are both counted when both concatenations match.

Example 1

Input
nums = ["20","26","2026","202","6"], target = "2026"
Output
2
Explanation
`"20" + "26"` and `"202" + "6"`.

Example 2

Input
nums = ["7","7","7"], target = "77"
Output
6
Explanation
Any two different indices work, in either order: 3 × 2 = 6 pairs.

Example 3

Input
nums = ["1","23"], target = "231"
Output
1
Explanation
Only `nums[1] + nums[0]`.

Constraints

  • 2 <= nums.length <= 100
  • 1 <= nums[i].length <= 100
  • 2 <= target.length <= 100
  • nums[i] and target consist of digits
  • nums[i] and target have no leading zeros
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} nums
 * @param {string} target
 * @return {number}
 */
var numOfPairs = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Pairs of Strings With Concatenation Equal to Target Solution

Number of Pairs of Strings With Concatenation Equal to Target solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Pairs of Strings With Concatenation Equal to Target is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Hash Table, Counting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums of digit strings and a digit string target.

Count the pairs of indices (i, j) with i != j such that the concatenation nums[i] + nums[j] equals target. Pairs are ordered: (i, j) and (j, i) are different pairs and are both counted when both concatenations match.

Example 1

Input: nums = ["20","26","2026","202","6"], target = "2026"
Output: 2
Explanation: `"20" + "26"` and `"202" + "6"`.

Example 2

Input: nums = ["7","7","7"], target = "77"
Output: 6
Explanation: Any two different indices work, in either order: 3 × 2 = 6 pairs.

Example 3

Input: nums = ["1","23"], target = "231"
Output: 1
Explanation: Only `nums[1] + nums[0]`.

Constraints

  • 2 <= nums.length <= 100
  • 1 <= nums[i].length <= 100
  • 2 <= target.length <= 100
  • nums[i] and target consist of digits
  • nums[i] and target have no leading zeros

Hints for Number of Pairs of Strings With Concatenation Equal to Target

  1. Hint 1

    Checking every pair works for 100 strings, but there is a cleaner count.

  2. Hint 2

    A matching pair splits target into a non-empty prefix and a non-empty suffix. There are only target.length - 1 split points.

  3. Hint 3

    Count how many times each string occurs. For each split, multiply the prefix's count by the suffix's count — and when prefix and suffix are the same string, use c × (c - 1) so an index is never paired with itself.

How to solve Number of Pairs of Strings With Concatenation Equal to Target

Every valid pair corresponds to a split of target into prefix + suffix, so count string frequencies and sum over the split points.

Approach

  1. Count how many times each string appears in nums.
  2. For each split point k from 1 to target.length - 1, let pre = target[0:k] and suf = target[k:].
  3. If pre != suf, add count[pre] × count[suf]: any index holding pre pairs with any index holding suf, and they are automatically different indices.
  4. If pre == suf, add count[pre] × (count[pre] - 1): ordered pairs of two different indices among the copies.

Why it works

A pair (i, j) matches exactly when nums[i] is the prefix of target of length len(nums[i]) and nums[j] is the rest, so each matching pair is counted at exactly one split point (the one at len(nums[i])). Within a split, the number of ordered index pairs is the product of the two counts, minus the forbidden i == j pairs, which only exist when the two pieces are the same string.

Complexity

  • Time — O(n·L + L²) where L is the target length
  • Space — O(n·L) for the counts

Pitfalls

  • When the prefix equals the suffix ("7" + "7"), count² would pair an index with itself.
  • Pairs are ordered — do not divide by two.
  • Both pieces must be non-empty, so the split runs from 1 to L - 1.

Reference solution

Python

from typing import List
from collections import Counter

def numOfPairs(nums: List[str], target: str) -> int:
    cnt = Counter(nums)
    total = 0
    for k in range(1, len(target)):
        pre, suf = target[:k], target[k:]
        if pre == suf:
            total += cnt[pre] * (cnt[pre] - 1)
        else:
            total += cnt[pre] * cnt[suf]
    return total

Java

public static int numOfPairs(String[] nums, String target) {
    Map<String, Integer> cnt = new HashMap<>();
    for (String s : nums) cnt.merge(s, 1, Integer::sum);
    int total = 0;
    for (int k = 1; k < target.length(); k++) {
        String pre = target.substring(0, k), suf = target.substring(k);
        int a = cnt.getOrDefault(pre, 0);
        if (pre.equals(suf)) total += a * (a - 1);
        else total += a * cnt.getOrDefault(suf, 0);
    }
    return total;
}

C++

int numOfPairs(vector<string>& nums, string target) {
    unordered_map<string, int> cnt;
    for (auto& s : nums) cnt[s]++;
    int total = 0;
    for (size_t k = 1; k < target.size(); k++) {
        string pre = target.substr(0, k), suf = target.substr(k);
        int a = cnt.count(pre) ? cnt[pre] : 0;
        if (pre == suf) total += a * (a - 1);
        else total += a * (cnt.count(suf) ? cnt[suf] : 0);
    }
    return total;
}

JavaScript

var numOfPairs = function(nums, target) {
    var cnt = new Map();
    for (var i = 0; i < nums.length; i++) cnt.set(nums[i], (cnt.get(nums[i]) || 0) + 1);
    var total = 0;
    for (var k = 1; k < target.length; k++) {
        var pre = target.slice(0, k), suf = target.slice(k);
        var a = cnt.get(pre) || 0;
        total += pre === suf ? a * (a - 1) : a * (cnt.get(suf) || 0);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings