We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Pairs of Strings With Concatenation Equal to Target

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires finding pairs of strings whose concatenation results in the target string.
  • The order of the strings matters as (i, j) is different from (j, i).
  • A hash map can be used to store the occurrences of each string for efficient lookup.
  • The length of the strings provides bounds on potential pairs, as only strings that can concatenate to form the target should be considered.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of strings in nums and m is the average length of the strings. Space Complexity: O(n) for storing the counts of strings in a hash map.

Solution

To solve the problem, we can use a hash map to store the counts of each string in the nums array. For each string, we will check if there exists another string that can concatenate with it to form the target. We will iterate over each string in nums, split the target into two potential parts, and check if both parts exist in the hash map. If the parts are the same, we need to ensure that we do not count the same index twice. This approach guarantees that we efficiently find all valid pairs.

Code Solutions

def count_pairs(nums, target):
    count = 0
    freq = {}
    
    # Count occurrences of each string in nums
    for num in nums:
        freq[num] = freq.get(num, 0) + 1

    # Iterate over each string and find valid pairs
    for num in nums:
        # Check if target starts with num
        if target.startswith(num):
            # Determine the required suffix to form the target
            suffix = target[len(num):]
            if suffix in freq:
                count += freq[suffix]
                # If the suffix is the same as num, we should reduce the count by 1
                if suffix == num:
                    count -= 1

    # Each pair (i, j) is counted twice, so return half of the count
    return count * 2
← Back to All Questions