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).
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; }}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.