LeetCode 2023 - Number of Pairs of Strings With Concatenation Equal to Target

LeetCode Problem 2023

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Counting

Solution

Problem Understanding

The problem asks us to find the number of ordered pairs of indices (i, j) in a list of digit strings nums such that concatenating nums[i] and nums[j] produces exactly the string target. It is important that i and j are distinct, meaning the same element cannot pair with itself in the same position.

The input nums is an array of strings, where each string consists of digits only, and target is also a string of digits. The output is a single integer representing how many valid concatenation pairs exist.

The constraints tell us that nums has at most 100 elements, and the length of each string and the target is at most 100. This allows solutions with time complexity up to O(n²) to work, but any approach that can reduce unnecessary repeated work will be more efficient and elegant.

Key edge cases include when multiple identical strings exist in nums, or when parts of target match multiple elements. For example, nums = ["1","1","1"] and target = "11" results in multiple combinations due to repetition. Another edge case is when no concatenation is possible.

Approaches

Brute Force

The brute-force approach is straightforward: iterate through all pairs (i, j) where i != j, concatenate nums[i] + nums[j], and check if it equals target. If it does, increment a counter. This guarantees correctness because it examines all possible pairs. However, its time complexity is O(n² * m), where n is the length of nums and m is the average length of the strings, because each concatenation requires up to m operations. Given the problem constraints, this is acceptable but not optimal.

Optimized Approach Using Hash Map

A better approach leverages the observation that for a valid pair (i, j) where nums[i] + nums[j] = target, the second string nums[j] must be the suffix of target after removing nums[i] from the start, and vice versa. We can use a hash map (dictionary) to count the frequency of strings in nums. Then for each string, we check if the target starts with that string and whether the corresponding suffix exists in the map. We multiply the counts to account for all combinations. Special care is needed when the prefix and suffix are identical, to avoid counting the same index twice.

This approach reduces the redundant concatenation checks, making it more efficient in practice.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² * m)	O(1)	Check all pairs (i,j) explicitly.
Hash Map Optimized	O(n * m)	O(n)	Use string count map and suffix check to count valid pairs efficiently.

Algorithm Walkthrough

1. Initialize a hash map count_map to store the frequency of each string in nums.
2. Iterate through nums and populate count_map with the count of each string.
3. Initialize a variable result to 0 to store the number of valid pairs.
4. For each string s in nums, compute the potential suffix by checking if target starts with s.
5. If the target starts with s, the remaining substring suffix = target[len(s):] must exist in count_map.
6. Add count_map[suffix] to result if suffix is in the map. If suffix is equal to s, subtract 1 to avoid counting the same index twice.
7. Return result.

Why it works: The algorithm guarantees correctness because for every potential prefix in nums, it only counts suffixes that exist in nums and correctly handles duplicate elements. The hash map ensures counting occurs in O(1) per check.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        count_map = Counter(nums)
        result = 0
        
        for s in nums:
            if target.startswith(s):
                suffix = target[len(s):]
                if suffix in count_map:
                    result += count_map[suffix]
                    if suffix == s:
                        result -= 1
        return result

The Python solution uses Counter to quickly count occurrences. For each string in nums, it checks if it is a prefix of target, then computes the suffix and looks up its count. If the prefix equals the suffix, it adjusts the count to avoid pairing the same element with itself. This follows the algorithm steps exactly.

Go Solution

func numOfPairs(nums []string, target string) int {
    countMap := make(map[string]int)
    for _, s := range nums {
        countMap[s]++
    }

    result := 0
    for _, s := range nums {
        if len(s) <= len(target) && target[:len(s)] == s {
            suffix := target[len(s):]
            if countMap[suffix] > 0 {
                result += countMap[suffix]
                if s == suffix {
                    result--
                }
            }
        }
    }
    return result
}

In Go, we use a map to count frequencies. We check each string as a prefix of target, compute the suffix, and increment result by the frequency. The check if s == suffix ensures we don't count the same index. Go requires careful string slicing and length checks to avoid out-of-range errors.

Worked Examples

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

Iteration	s	target.startswith(s)?	suffix	count_map[suffix]	result
0	"777"	Yes	"7"	1	1
1	"7"	Yes	"777"	1	2
2	"77"	Yes	"77"	2	4
3	"77"	Yes	"77"	2	6 (adjusted - duplicate handled in code) final 4

Example 2: nums = ["123","4","12","34"], target = "1234"

Iteration	s	suffix	count_map[suffix]	result
"123"	"4"	1	1
"4"	not prefix	-	-
"12"	"34"	1	2
"34"	not prefix	-	-

Example 3: nums = ["1","1","1"], target = "11"

Each "1" pairs with the other two "1"s, giving 6 valid pairs.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m)	Iterate over n strings, slicing and comparing strings of length up to m.
Space	O(n)	Hash map stores frequency of all n strings.

The hash map avoids redundant O(n²) pair checks, reducing runtime while using linear additional space.

Test Cases

# Provided examples
assert Solution().numOfPairs(["777","7","77","77"], "7777") == 4  # multiple valid pairs
assert Solution().numOfPairs(["123","4","12","34"], "1234") == 2  # straightforward concatenations
assert Solution().numOfPairs(["1","1","1"], "11") == 6  # repeated elements

# Edge cases
assert Solution().numOfPairs(["1","2"], "12") == 1  # simple two element array
assert Solution().numOfPairs(["1","2"], "21") == 1  # order matters
assert Solution().numOfPairs(["1"], "11") == 0  # single element, cannot pair with itself
assert Solution().numOfPairs(["1","11"], "111") == 2  # mix of lengths
assert Solution().numOfPairs(["10","01","0"], "1001") == 1  # substring matches

Test	Why
["777","7","77","77"], "7777"	Multiple repeated strings, ensures counting handles duplicates correctly
["123","4","12","34"], "1234"	Normal case, multiple ways to concatenate
["1","1","1"], "11"	All identical elements, ensure multiple combinations counted
["1","2"], "12"	Minimal array, basic concatenation
["1","2"], "21"	Order-sensitive concatenation
["1"], "11"	Single element cannot pair
["1","11"], "111"	Different string lengths
["10","01","0"], "1001"	Substrings overlapping, complex match

Edge Cases

1. Multiple identical strings: When nums contains repeated strings, the number of valid pairs can grow combinatorially. For instance, ["1","1","1"] with target = "11" has 6 valid pairs. Our hash map solution correctly multiplies the counts and adjusts for same-index pairs.

2. Prefix equals suffix: When the prefix string is identical to the suffix, we