Skip to main content
Talentd

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

MediumArrayHash TableStringCounting20 min readAsked at: Apple, Capital One
Practice this problem

Problem Statement

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.

Approach Overview

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.

Approach 1: Divide and Conquer Approach

This approach employs the classic divide and conquer strategy to efficiently solve the problem by breaking it down into smaller sub-problems. Each smaller problem is solved independently before combining their results to arrive at the final solution. Common examples include algorithms like merge sort or quicksort.

This C implementation uses the merge sort algorithm, which is a classic example of a divide and conquer approach. First, we split the array into two halves, recursively sort each half, and then merge the sorted halves. Recursion ensures each half is broken down until single-element or empty subarrays are reached, which are trivially sorted. The merge function is then used to combine them back into sorted order.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) - This complexity arises as each level of recursion processes n elements and the depth of recursion is log n.
Space Complexity: O(n) - Requires additional temporary storage for merging.

Try this approach in the editor →

Approach 2: Iterative In-Place Sorting

This approach focuses on sorting algorithms that perform sorting in-place, using an iterative technique instead of recursion. These algorithms generally have lower space overhead as they operate directly on the input data and are characterized by the use of loops to iterate over the array.

This C solution employs the insertion sort algorithm, an example of an in-place, iterative sorting algorithm. The array is processed element by element, comparing each with its predecessors to find the correct insertion point, thus organizing the array in ascending order iteratively.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) - The worst case involves each pair of elements being compared and swapped.
Space Complexity: O(1) - Sorting is performed in-place without requiring extra space.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n^2 times m), where n and m are the lengths of the array nums and the string target, respectively. The space complexity is O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 4: 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.

The time complexity is O(n + m^2), and the space complexity is O(n). Here, n and m are the lengths of the array nums and the string target, respectively.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Divide and Conquer Approach

Time Complexity: O(n log n) - This complexity arises as each level of recursion processes n elements and the depth of recursion is log n.
Space Complexity: O(n) - Requires additional temporary storage for merging.

Iterative In-Place Sorting

Time Complexity: O(n^2) - The worst case involves each pair of elements being compared and swapped.
Space Complexity: O(1) - Sorting is performed in-place without requiring extra space.

Enumeration—
Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n² * k)O(1)Small inputs or initial reasoning during interviews
Divide and Conquer on Target Splits (Hash Map Counting)O(n + m)O(n)General case; fastest and most common interview solution
Iterative In-Place Sorting + Binary SearchO(n log n + n * k)O(1)–O(log n)When memory is constrained or hash tables are undesirable

Video Solution

Number Of Pairs Of Strings With Concatenation Equal To Target|Leetcode 2023|Biweekly 62|Java| Hindi • Pepcoding • 1,544 views views

Watch 8 more video solutions →

Frequently Asked Questions

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.
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.
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.
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.

Ready to solve this problem?

Practice Number of Pairs of Strings With Concatenation Equal to Target with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum