Number of Pairs of Strings With Concatenation Equal to Target - Solution & Explanation

Problem Overview: You get an array nums of strings and a string target. Count ordered pairs (i, j) where i != j and nums[i] + nums[j] == target. The challenge is avoiding the obvious O(n²) pair check.

Approach 1: Divide and Conquer on Target Splits (Hash Counting) (Time: O(n + m), Space: O(n))

The key observation: any valid pair must split the target into a prefix and suffix. If target = prefix + suffix, then you only need strings equal to prefix and suffix. Build a frequency map using a hash table for all strings in nums. Iterate over every possible split of the target string. For each split, multiply the counts of the prefix and suffix from the map.

Special care is required when prefix == suffix. In that case, pairs must use different indices, so the number of ordered pairs becomes count * (count - 1). This approach effectively divides the target into independent prefix/suffix subproblems and uses constant-time hash lookups to count matches.

The runtime depends mainly on building the frequency map and scanning the target splits. Hash lookups are O(1) on average, making this the most practical solution. It heavily relies on efficient string matching and frequency counting.

Approach 2: Iterative In-Place Sorting with Binary Search (Time: O(n log n + n * k), Space: O(1) or O(log n))

Another approach sorts the array of strings first. After sorting, iterate through each string and check whether it can form the prefix of target. If it matches the prefix, compute the required suffix and locate it using binary search in the sorted array.

Because the array is sorted, duplicate strings appear in contiguous ranges. You can count how many matches exist for the suffix and accumulate valid pair counts while ensuring indices are different when prefix and suffix are identical. This method avoids an explicit hash map and keeps auxiliary memory minimal.

The tradeoff is additional sorting cost and repeated substring checks on the string. Still, it performs well when memory usage must stay low or when the input is already partially sorted.

Recommended for interviews: The hash table counting approach based on splitting the target is what most interviewers expect. It reduces the naive O(n²) pair comparison to near linear time and clearly demonstrates pattern recognition with prefix/suffix decomposition. Showing the brute-force idea first proves correctness, but the hash-based counting solution demonstrates stronger algorithmic thinking.