# Number of Pairs of Strings With Concatenation Equal to Target
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target)
Canonical: https://scaleengineer.com/dsa/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
---
## Problem
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.

# Approaches
## Brute Force Iteration
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.
**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).
**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).
### Explanation
```java
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;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use a nested loop to iterate through all possible pairs of indices `(i, j)` from the `nums` array.
- The outer loop runs for `i` from 0 to `n-1` (where `n` is `nums.length`).
- The inner loop runs for `j` from 0 to `n-1`.
- Inside the inner loop, check if `i` is not equal to `j`. This is a requirement of the problem.
- If `i != j`, concatenate `nums[i]` and `nums[j]`.
- Compare the concatenated string with the `target` string.
- If they are equal, increment the `count`.
- After the loops finish, return `count`.

## Optimized Approach using Hash Map and Target Splitting
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`.
**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.
**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.
### Explanation
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 the `count1` available strings. Since we need pairs of distinct indices, we can form `count1 * (count1 - 1)` ordered pairs. We add this to our total count.
- **Case 2: `prefix` and `suffix` are different**: We can match any of the `count1` prefixes with any of the `count2` suffixes. This gives `count1 * count2` pairs. We add this to our total.

By summing these values over all possible splits, we get the final answer.

```java
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;
    }
}
```
### Algorithm
- Create a hash map, `freq`, to store the frequency of each string in the `nums` array.
- Initialize a counter `ans` to 0.
- Iterate through all possible split points of the `target` string. A loop for `i` from 1 to `target.length() - 1` will achieve this.
- For each `i`, split `target` into `prefix = target.substring(0, i)` and `suffix = target.substring(i)`.
- Look up the frequencies of `prefix` and `suffix` in the `freq` map. Let these be `count1` and `count2`.
- If `prefix` and `suffix` are the same string, the number of valid pairs is `count1 * (count1 - 1)`. Add this to `ans`.
- If `prefix` and `suffix` are different, the number of pairs is `count1 * count2`. Add this to `ans`.
- Return the total `ans` after checking all splits.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
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))

```

### CPP

```cpp
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;
  }
};

```