2023. Number of Pairs of Strings With Concatenation Equal to Target

MediumArrayString
Leetcode Link

Problem Description

The given problem involves finding the total number of unique pairs of indices (i, j) from an array of digit strings nums such that when nums[i] and nums[j] are concatenated (joined together in the order nums[i] + nums[j]), the result equals the given digit string target. The constraint is that i and j must be different, i.e., you cannot use the same index twice in a pair. The task is to return the count of such pairs.

Intuition

To solve this problem, the insight is to use the properties of strings and hash tables. We know that if the concatenation of two strings, a and b, produces the target, then a must be a prefix of target, and b must be a suffix. Furthermore, a and b together must cover the entire target string without overlap, except when a and b are equal.

One approach would be to iterate over all possible pairs of strings in nums and check if their concatenation equals target. However, this approach would have a time complexity of O(n^2 * m), where n is the number of strings in nums and m is the length of target. We can optimize this by using a hash table (a Counter in Python) to store counts of all the strings in nums. This allows us to efficiently look up how many times a specific string occurs without iterating through the array again.

The solution iterates through each possible split point in target, effectively dividing the target into a prefix a and a suffix b. For each such pair (a, b), the product of the number of occurrences of a and b in nums is added to the answer. If a and b are the same, we adjust the count since we cannot use the same index twice; this is done by subtracting one from the count of a before multiplying.

This approach results in a time complexity of O(m^2 + n), where m is the length of target and n is the number of strings in nums, since we are iterating through the target string and using a hash table for constant time lookups.

Solution Approach

The solution approach can be summarized in the following steps:

  1. Initialize a Counter: A Counter from Python's collections module is initiated to store the occurrences of each string in nums. This data structure allows us to query in constant time whether a string is present in nums and, if so, how many times.

  2. Iterate through Target Splits: The approach then involves iterating through each possible index in the target string to split it into two parts, a and b. The indices chosen range from 1 to the length of the target string minus one. This ensures that a and b are non-empty and cover the whole target string when concatenated.

  3. Calculate Pair Combinations: For a given split (a, b):

    • If a is not equal to b, the number of valid pairs is the product of the occurrences of a and b in nums, since they can be freely paired.
    • If a is equal to b, one instance of a is subtracted from the total count before multiplication to avoid pairing a number with itself as i cannot be equal to j.

The final answer, stored in ans, accumulates the count of valid pairs through all iterations.

1class Solution:
2    def numOfPairs(self, nums: List[str], target: str) -> int:
3        cnt = Counter(nums)  # Step 1: Initialize a Counter
4        ans = 0  # Initialize the count of pairs to zero
5        for i in range(1, len(target)):  # Step 2: Iterate through Target Splits
6            a, b = target[:i], target[i:]  # Split the `target` into `a` and `b`
7            if a != b:  # Step 3: Calculate Pair Combinations
8                ans += cnt[a] * cnt[b]  # Multiply the counts if `a` and `b` are not equal
9            else:
10                ans += cnt[a] * (cnt[a] - 1)  # Adjust if `a` and `b` are the same
11        return ans # Return the final count of pairs

The current implementation is efficient because it avoids the brute-force checking of all pairs in nums, instead taking advantage of the hashing capability of the Counter to look up counts quickly.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small example where nums = ["1","11","111","011"] and target = "1111". Here's how the solution approach would be applied to find the count of pairs whose concatenation equals target.

  1. Initialize Counter: The Counter will count occurrences of all strings in nums.

    1Counter({'1': 1, '11': 1, '111': 1, '011': 1})

    This allows for constant-time queries of occurrences.

  2. Iterate through Target Splits: The target "1111" has several possible splits: "1|111", "11|11", and "111|1".

    • For the split "1|111":

      • a is "1", and b is "111".
      • The count of "1" in nums is 1, and the count of "111" is also 1.
      • Since a != b, we multiply their counts: 1 * 1 = 1.
    • For the split "11|11":

      • a is "11", and b is also "11".
      • The count of "11" in nums is 1.
      • But a == b, so we use the adjusted count: 1 * (1 - 1) = 0.
    • For the split "111|1":

      • a is "111", and b is "1".
      • The count of "111" in nums is 1, and the count of "1" is 1.
      • Since a != b, we multiply their counts: 1 * 1 = 1.
  3. Calculate Pair Combinations: Adding the results of all splits, we get 1 + 0 + 1 = 2.

So, there are 2 unique pairs of indices in nums that can be concatenated to form the target "1111".

Python Solution

1from collections import Counter
2
3class Solution:
4    def numOfPairs(self, nums: List[str], target: str) -> int:
5        # Create a counter to hold the frequency of each number in nums
6        num_counter = Counter(nums)
7      
8        # Initialize a variable to count the number of valid pairs
9        pair_count = 0
10      
11        # Iterate through the target string and split it at different points
12        for i in range(1, len(target)):
13            prefix, suffix = target[:i], target[i:]  # Split target into prefix and suffix
14          
15            # If prefix and suffix are different, multiply their counts directly
16            if prefix != suffix:
17                pair_count += num_counter[prefix] * num_counter[suffix]
18            else:
19                # If prefix and suffix are the same, we must avoid counting the pair (num, num) twice
20                pair_count += num_counter[prefix] * (num_counter[prefix] - 1)
21      
22        # Return the total number of pairs found
23        return pair_count
24

Java Solution

1class Solution {
2
3    public int numOfPairs(String[] nums, String target) {
4        // Create a map to store the frequency of each number (string) in the nums array
5        Map<String, Integer> countMap = new HashMap<>();
6        for (String num : nums) {
7            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
8        }
9
10        // Initialize a variable to keep track of the number of valid pairs
11        int answer = 0;
12
13        // Loop through the target string, excluding its first and last characters
14        for (int i = 1; i < target.length(); ++i) {
15            // Split the target into two substrings ("a" and "b") at the current position i
16            String a = target.substring(0, i);
17            String b = target.substring(i);
18          
19            // Retrieve the frequency of each substring from the map
20            int countA = countMap.getOrDefault(a, 0);
21            int countB = countMap.getOrDefault(b, 0);
22          
23            // If "a" and "b" are different, multiply their counts since they can form distinct pairs
24            if (!a.equals(b)) {
25                answer += countA * countB;
26            } else {
27                // If "a" and "b" are the same, each instance of "a" could pair with all other instances of "b", but not with itself
28                answer += countA * (countB - 1);
29            }
30        }
31
32        // Return the total number of valid pairs found
33        return answer;
34    }
35}
36

C++ Solution

1#include <string>
2#include <vector>
3#include <unordered_map>
4
5class Solution {
6public:
7    // Function to count the number of pairs of strings in 'nums' that can be concatenated to form the 'target' string.
8    int numOfPairs(std::vector<std::string>& nums, std::string target) {
9        // Using a hashmap to count the frequency of each string in 'nums'.
10        std::unordered_map<std::string, int> frequencyMap;
11        for (auto &num : nums) {
12            ++frequencyMap[num]; // Increment frequency count for each string.
13        }
14      
15        int pairCount = 0; // This will store the number of valid pairs found.
16
17        // Iterate over all possible splits of 'target' into two non-empty substrings 'leftPart' and 'rightPart'.
18        for (int i = 1; i < target.size(); ++i) {
19            std::string leftPart = target.substr(0, i);
20            std::string rightPart = target.substr(i);
21          
22            int leftCount = frequencyMap[leftPart], rightCount = frequencyMap[rightPart];
23          
24            // When 'leftPart' and 'rightPart' are different, multiply their frequencies directly.
25            // Otherwise, if they are the same (e.g., 'a' and 'a'), pairs are counted by forming combinations
26            // of two different indices from the frequency of that string; hence, the (rightCount - 1).
27            if (leftPart != rightPart) {
28                pairCount += leftCount * rightCount;
29            } else {
30                pairCount += leftCount * (rightCount - 1);
31            }
32        }
33      
34        return pairCount; // Return the total number of pairs.
35    }
36};
37

Typescript Solution

1type StringFrequencyMap = Record<string, number>;
2
3// Function to count the number of pairs of strings in the array that can be concatenated to form the target string.
4function numOfPairs(nums: string[], target: string): number {
5    // Creating a map to keep the frequency of each string in the array.
6    const frequencyMap: StringFrequencyMap = nums.reduce((acc: StringFrequencyMap, num: string) => {
7        acc[num] = (acc[num] || 0) + 1;
8        return acc;
9    }, {});
10
11    let pairCount = 0; // This will hold the total number of valid pairs found.
12
13    // Iterate over all possible non-empty prefixes and suffixes of the target string.
14    for (let i = 1; i < target.length; i++) {
15        const leftPart = target.slice(0, i);
16        const rightPart = target.slice(i);
17
18        const leftCount = frequencyMap[leftPart] || 0;
19        const rightCount = frequencyMap[rightPart] || 0;
20      
21        // If leftPart and rightPart are different, compute the product of their counts.
22        // If they are the same, we must choose different elements, hence the product of leftCount and (rightCount - 1).
23        if (leftPart !== rightPart) {
24            pairCount += leftCount * rightCount;
25        } else {
26            pairCount += leftCount * (rightCount - 1);
27        }
28    }
29
30    // Return the computed number of pairs.
31    return pairCount;
32}
33

Time and Space Complexity

Time Complexity

The time complexity of the given code is composed of two parts: the creation of the counter and the loop that goes through the possible splits of the target string.

  • Constructing cnt as a Counter object takes O(n) time, where n is the number of elements in nums, because it needs to iterate over all elements once to count the frequencies.
  • For the loop that checks all the possible splits, the number of iterations is proportional to the length of the target string because it iterates through every possible split index. This is O(m), where m is the length of the target string.
  • The operations within the loop take constant time since dictionary access and multiplication are O(1) operations.

Therefore, the overall time complexity is O(n + m).

Space Complexity

The space complexity is primarily influenced by the storage requirements of the Counter object.

  • The Counter object cnt stores each unique element from nums. In the worst case, all elements are unique, so the space required is O(n), where n is the number of elements in nums.

Thus, the space complexity of the code is O(n).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫