Number of Pairs of Strings With Concatenation Equal to Target
MedPrompt
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 <= 1001 <= nums[i].length <= 1002 <= target.length <= 100nums[i]andtargetconsist of digits.nums[i]andtargetdo not have leading zeros.
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to simulate the process directly. We can check every possible ordered pair of strings from the input array. We use two nested loops to generate all pairs of indices (i, j). For each pair, we must ensure that i is not equal to j as per the problem statement. Then, we concatenate the strings nums[i] and nums[j] and check if the resulting string is identical to the target string. If it is, we increment a counter. After checking all pairs, the value of the counter is our answer.
Algorithm
- Initialize a counter
countto 0. - Use a nested loop to iterate through all possible pairs of indices
(i, j)from thenumsarray. - The outer loop runs for
ifrom 0 ton-1(wherenisnums.length). - The inner loop runs for
jfrom 0 ton-1. - Inside the inner loop, check if
iis not equal toj. This is a requirement of the problem. - If
i != j, concatenatenums[i]andnums[j]. - Compare the concatenated string with the
targetstring. - If they are equal, increment the
count. - After the loops finish, return
count.
Walkthrough
class Solution { public int numOfPairs(String[] nums, String target) { int count = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // The problem requires pairs of different indices. if (i == j) { continue; } // In Java, the '+' operator concatenates strings. // The .equals() method compares string content. if ((nums[i] + nums[j]).equals(target)) { count++; } } } return count; }}Complexity
Time
O(N^2 * L), where N is the number of strings in `nums` and L is the length of the `target` string. The two nested loops run in O(N^2) time. Inside the loops, string concatenation takes O(L) time, and string comparison also takes O(L) time.
Space
O(L), where L is the length of the `target` string. This space is used to store the temporary concatenated string. The auxiliary space complexity, not counting this temporary storage, is O(1).
Trade-offs
Pros
Simple to understand and implement.
Requires minimal extra space.
Cons
Inefficient due to its quadratic time complexity with respect to the input array size (
N).Performs many redundant string operations (concatenation and comparison).
A more efficient approach avoids the O(N^2) complexity by changing the perspective. Instead of building pairs from nums and checking against target, we can deconstruct target and see if its components exist in nums. We can iterate through all possible ways to split the target string into two non-empty parts: a prefix and a suffix. For each such split, we need to count how many pairs (nums[i], nums[j]) exist where nums[i] equals the prefix and nums[j] equals the suffix. To do this efficiently, we first pre-process the nums array and store the frequency of each string in a hash map. This allows for O(1) average time lookups for the counts of our prefix and suffix.
Algorithm
- Create a hash map,
freq, to store the frequency of each string in thenumsarray. - Initialize a counter
ansto 0. - Iterate through all possible split points of the
targetstring. A loop forifrom 1 totarget.length() - 1will achieve this. - For each
i, splittargetintoprefix = target.substring(0, i)andsuffix = target.substring(i). - Look up the frequencies of
prefixandsuffixin thefreqmap. Let these becount1andcount2. - If
prefixandsuffixare the same string, the number of valid pairs iscount1 * (count1 - 1). Add this toans. - If
prefixandsuffixare different, the number of pairs iscount1 * count2. Add this toans. - Return the total
ansafter checking all splits.
Walkthrough
First, we populate a HashMap<String, Integer> with the counts of each string in nums. Then, we loop from i = 1 to target.length() - 1. In each iteration, i represents the length of the prefix. We extract the prefix = target.substring(0, i) and suffix = target.substring(i). We then fetch their counts, say count1 and count2, from our map.
- Case 1:
prefix.equals(suffix): If the two parts are identical, we need to form pairs from thecount1available strings. Since we need pairs of distinct indices, we can formcount1 * (count1 - 1)ordered pairs. We add this to our total count. - Case 2:
prefixandsuffixare different: We can match any of thecount1prefixes with any of thecount2suffixes. This givescount1 * count2pairs. We add this to our total.
By summing these values over all possible splits, we get the final answer.
import java.util.HashMap;import java.util.Map; class Solution { public int numOfPairs(String[] nums, String target) { Map<String, Integer> freq = new HashMap<>(); for (String num : nums) { freq.put(num, freq.getOrDefault(num, 0) + 1); } int count = 0; int len = target.length(); for (int i = 1; i < len; i++) { String prefix = target.substring(0, i); String suffix = target.substring(i); long count1 = freq.getOrDefault(prefix, 0); long count2 = freq.getOrDefault(suffix, 0); if (prefix.equals(suffix)) { // If we have k identical strings, we can form k * (k-1) ordered pairs. count += count1 * (count1 - 1); } else { // If strings are different, we can form count1 * count2 pairs. count += count1 * count2; } } return count; }}Complexity
Time
O(N * K + L^2), where N is the length of `nums`, K is the maximum length of a string in `nums`, and L is the length of `target`. Building the frequency map takes O(N * K). The main loop runs L-1 times, and inside the loop, string operations (substring, hashing for map lookup) take O(L) time.
Space
O(N * K), where N is the number of strings in `nums` and K is the average length of a string. This space is required for the hash map to store the frequencies of up to N unique strings.
Trade-offs
Pros
Significantly more efficient than the brute-force approach, with time complexity related to the lengths of the input arrays and target string rather than the square of the array size.
The logic is clean and directly addresses the structure of the problem.
Cons
Requires extra space to store the frequency map, which can be significant if there are many long, unique strings.
Solutions
Solution
class Solution {public int numOfPairs(String[] nums, String target) { int n = nums.length; int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i != j && target.equals(nums[i] + nums[j])) { ++ans; } } } return ans; }}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))class Solution {public: int numOfPairs(vector<string> &nums, string target) { int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i != j && nums[i] + nums[j] == target) ++ans; } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.