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 <= 1001 <= nums[i].length <= 1002 <= target.length <= 100nums[i] and target consist of digitsnums[i] and target have no leading zeros
Hints for Number of Pairs of Strings With Concatenation Equal to Target
Hint 1
Checking every pair works for 100 strings, but there is a cleaner count.
Hint 2
A matching pair splits
targetinto a non-empty prefix and a non-empty suffix. There are onlytarget.length - 1split points.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
- Count how many times each string appears in
nums. - For each split point
kfrom 1 totarget.length - 1, letpre = target[0:k]andsuf = target[k:]. - If
pre != suf, addcount[pre] × count[suf]: any index holdingprepairs with any index holdingsuf, and they are automatically different indices. - If
pre == suf, addcount[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 totalJava
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.