Number of Pairs of Strings With Concatenation Equal to Target Python/Java solution

Most Python and Java implementations build a HashMap or dictionary of string frequencies. The algorithm then iterates over every possible split of the target and counts matching prefix–suffix pairs using constant-time lookups. This implementation typically runs in O(n + m) time and O(n) space.

What is the best approach for Number of Pairs of Strings With Concatenation Equal to Target?

The most efficient approach uses a hash table to store frequencies of all strings in the array. Split the target into every possible prefix and suffix and look up both parts in the map. Multiply their counts to compute how many pairs form the target. This reduces the complexity to roughly O(n + m) with O(n) extra space.

Is Number of Pairs of Strings With Concatenation Equal to Target asked at Google/Amazon/Meta?

String pairing and hash-map counting problems are common interview patterns at companies like Google, Amazon, and Meta. Variations often involve concatenation checks, prefix–suffix decomposition, or counting valid string combinations efficiently.

What data structure is used in Number of Pairs of Strings With Concatenation Equal to Target?

The primary data structure is a hash table (hash map) that stores the frequency of each string in the input array. It enables constant-time lookup when checking whether a required prefix or suffix exists. Arrays and basic string operations are also used for iteration and substring checks.

What is the time complexity of Number of Pairs of Strings With Concatenation Equal to Target?

The optimal hash-map counting solution runs in O(n + m) time, where n is the number of strings and m is the length of the target. Building the frequency map takes O(n), and checking all prefix–suffix splits of the target takes O(m). Space complexity is O(n) for storing string counts.

Description Hints 2 Solution Video 6:23

2023. Number of Pairs of Strings With Concatenation Equal to Target

Q: Is Number of Pairs of Strings With Concatenation Equal to Target easy or hard?

This problem is rated Medium because the brute-force solution is straightforward but inefficient at O(n²). Recognizing that the target can be split into prefix and suffix components and solved using hash-map counting is the key insight that reduces the complexity significantly.

Q: How to solve Number of Pairs of Strings With Concatenation Equal to Target in O(n)?

Store every string in a hash map with its frequency. Iterate through every possible split of the target string into prefix and suffix. For each split, retrieve the counts of both parts from the map and add their pair combinations, adjusting when prefix equals suffix to avoid using the same index twice.

Medium75.6% acceptance2 companies

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 1:

Input: nums = ["777","7","77","77"], target = "7777"
Output: 4
Explanation: Valid pairs are:
- (0, 1): "777" + "7"
- (1, 0): "7" + "777"
- (2, 3): "77" + "77"
- (3, 2): "77" + "77"

Example 2:

Input: nums = ["123","4","12","34"], target = "1234"
Output: 2
Explanation: Valid pairs are:
- (0, 1): "123" + "4"
- (2, 3): "12" + "34"

Example 3:

Input: nums = ["1","1","1"], target = "11"
Output: 6
Explanation: Valid pairs are:
- (0, 1): "1" + "1"
- (1, 0): "1" + "1"
- (0, 2): "1" + "1"
- (2, 0): "1" + "1"
- (1, 2): "1" + "1"
- (2, 1): "1" + "1"

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 do not have leading zeros.

Asked at 2 companies

Capital One Apple

Topics

Hints open one at a time

Hint 1

Try to concatenate every two different strings from the list.

Hint 2

Count the number of pairs with concatenation equals to target.

6:23

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution