Number of Pairs of Strings With Concatenation Equal to Target

Number of Pairs of Strings With Concatenation Equal to Target

What is this problem about?

The Number of Pairs of Strings With Concatenation Equal to Target problem gives you an array of strings and a target string. Count the number of pairs (i, j) where i ≠ j and nums[i] + nums[j] == target (string concatenation). This coding problem uses a prefix-suffix hash map approach.

Why is this asked in interviews?

Apple asks this to test efficient prefix/suffix matching using hash maps. Brute force checks all pairs in O(n²). The efficient solution precomputes how many strings match each prefix of target, then for each string checks if it's a valid suffix. The array, hash table, counting, and string interview pattern is demonstrated.

Algorithmic pattern used

Prefix frequency map + suffix scan. Build a frequency map of all strings in nums. For each string s in nums: if target starts with s (s is a valid prefix), check if target[len(s):] exists in the frequency map. Add its frequency to the result. Handle the case where s == target[len(s):] carefully (don't double-count or exclude valid pairs where i=j is disallowed).

Example explanation

nums=["777","7","77","77"], target="7777".

• "7": prefix of "7777". Suffix "777" → count "777" in nums = 1. Add 1.
• "77": prefix of "7777". Suffix "77" → count "77" = 2. Add 2.
• "777": prefix of "7777". Suffix "7" → count "7" = 1. Add 1.
• "7777": check if prefix → yes (full string). Suffix "" → no empty string. Add 0. Total = 1+2+1+2 = 6 (including both "77" entries). Careful with pairs: answer = 4.

Common mistakes candidates make

• Brute force O(n²) string concatenation check.
• Not handling when the same string appears multiple times.
• Counting pair (i,j) where i==j (the problem requires i≠j).
• Off-by-one in prefix vs suffix split position.

Interview preparation tip

String concatenation pair problems always reduce to "prefix/suffix split" with hash map lookup. For target T: for each possible split point, check if count(T[:k]) pairs with count(T[k:]). Iterate all strings as potential prefixes. Use a frequency map for O(1) suffix lookup. The i≠j constraint requires care when prefix == suffix (subtract 1 if they refer to the same element). Practice splitting and matching patterns on concatenation problems.