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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Pairs of Strings With Concatenation Equal to Target

Number: 2133

Difficulty: Medium

Paid? No

Companies: Visa, Apple

Problem Description

Given an array of digit strings nums and a digit string target, count the number of distinct pairs of indices (i, j) with i ≠ j such that the concatenation of nums[i] and nums[j] is exactly equal to target.

Key Insights

  • The target string can only be formed by concatenating two strings from nums if it can be split into two non-empty parts.
  • Use a frequency dictionary (hash table) to count occurrences of each string in nums.
  • Iterate over all possible splits of target: let left be the prefix and right be the suffix.
  • For each split, if both parts are present in nums, update the result by multiplying their frequencies (taking care if both parts are identical, in which case pairs are counted as freq * (freq - 1)).

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of strings in nums and m is the length of the target (since we try all splits of target). Space Complexity: O(n) for storing the frequency counts.

Solution

We build a frequency hash table to count the occurrences of each string in nums. Then, for each possible split of the target string (from index 1 to len(target)-1), we extract the left (prefix) and right (suffix) parts. If both exist in our frequency dictionary, we add to our answer:

  • If the prefix and suffix are different, the number of valid pairs is freq(prefix) * freq(suffix).
  • If they are the same, we must choose two different indices from the frequency count, which gives freq(prefix) * (freq(prefix) - 1).

This gives us the required number of pairs.

Code Solutions

# Python solution
def numOfPairs(nums, target):
    # Build frequency dictionary for all strings in nums
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1

    count = 0
    # Iterate over all possible split positions in target
    for i in range(1, len(target)):
        prefix = target[:i]   # left part of the target
        suffix = target[i:]   # right part of the target
        
        if prefix in freq and suffix in freq:
            # If both parts are the same, count pairs using permutation formula
            if prefix == suffix:
                count += freq[prefix] * (freq[prefix] - 1)
            else:
                count += freq[prefix] * freq[suffix]
    return count

# Example usage:
print(numOfPairs(["777","7","77","77"], "7777"))
← Back to All Questions