#2023

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Pairs of Strings With Concatenation Equal to Target

Count all unique index pairs in a string array whose concatenation exactly matches the given target string using efficient hashing.

array hash table string counting

Problem Statement

Given an array of digit strings nums and a digit string target, determine how many ordered pairs of indices (i, j) with i not equal to j exist such that concatenating nums[i] and nums[j] forms target.

Return the total number of such pairs. For example, given nums = ["777","7","77","77"] and target = "7774", you must count each valid combination where the first string plus the second string equals target exactly.

Examples

Example 1

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

Output: 4

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

Valid pairs are:

(0, 1): "123" + "4"
(2, 3): "12" + "34"

Example 3

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

Output: 6

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.

Solution Approach

Use a Hash Map for Counting

Create a hash map storing the frequency of each string in nums. Then for each string, check if the target starts with it and whether the corresponding suffix exists in the map. Multiply the occurrences appropriately and exclude self-pairing if needed.

Scan Array with Prefix-Suffix Check

Iterate over nums, treating each element as a potential prefix. For each prefix, calculate the required suffix by removing the prefix from target. Lookup this suffix in the hash map to count valid pairs efficiently without nested loops for all pairs.

Handle Duplicate Strings Carefully

Since nums can contain duplicates, ensure that when counting pairs where the prefix equals the suffix, you subtract the current index to avoid counting a string with itself. Accumulate counts across all elements to get the final answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * k) where n is the number of strings and k is the average string length, dominated by substring and hash lookups. Space complexity is O(n) for the hash map storing string counts.

What Interviewers Usually Probe

Looking for use of hash map to reduce naive O(n^2) pair checks.
Interested in handling duplicate strings correctly without overcounting.
Expect candidates to separate prefix and suffix logic clearly.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude self-pairs when prefix equals suffix.
Miscounting duplicates by not using frequency map properly.
Using nested loops over all pairs which can be slow for larger arrays.

Follow-up variants

Count pairs for a target concatenation with at most one character difference.
Find pairs of strings whose concatenation is a palindrome.
Return the actual list of index pairs instead of just the count.

FAQ

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

Use a hash map to store string frequencies and scan the array checking each string as a prefix, then count matching suffixes.

Can we use nested loops for this problem?

Yes, but nested loops yield O(n^2) complexity and can be inefficient; hash-based scanning is faster and safer.

How do duplicates in nums affect counting?

Duplicates require careful handling to avoid counting the same index with itself and to multiply counts correctly using the frequency map.

Does the order of concatenation matter?

Yes, (i, j) and (j, i) are considered different pairs if nums[i] + nums[j] and nums[j] + nums[i] both equal the target.

What is the pattern this problem emphasizes?

It emphasizes the array scanning plus hash lookup pattern for counting valid string concatenations efficiently.

terminal

Solution

Solution 1: Enumeration

Traverse the array `nums`, for each $i$, enumerate all $j$, if $i \neq j$ and $nums[i] + nums[j] = target$, then increment the answer by one.

1

2

3

4

5

6

class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        n = len(nums)
        return sum(
            i != j and nums[i] + nums[j] == target for i in range(n) for j in range(n)
        )

Solution 2: Hash Table

We can use a hash table to count the occurrence of each string in the array `nums`, then traverse all prefixes and suffixes of the string `target`. If both the prefix and suffix are in the hash table, then increment the answer by the product of their occurrences.

1

2

3

4

5

6

class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        n = len(nums)
        return sum(
            i != j and nums[i] + nums[j] == target for i in range(n) for j in range(n)
        )

Continue Practicing

#2053 kth distinct string in an array #2085 count common words with one occurrence #2131 longest palindrome by concatenating two letter words