algoadvance

Leetcode 3042. Count Prefix and Suffix Pairs I

Problem Statement

Given two strings s1 and s2, you are asked to count the number of pairs (i, j) such that the prefix of s1 ending at index i and the suffix of s2 starting at index j are the same. Note that a prefix of s1 ending at index i is the substring of s1 from the start up to i, and a suffix of s2 starting at index j is the substring of s2 from j to the end.

Clarifying Questions

  1. Can the strings contain any characters?
    • Yes, the strings can contain any valid characters.
  2. What are the lengths of the strings?
    • No specific length is mentioned, so we should assume s1 and s2 can be of any length within typical constraints.
  3. Are the strings always non-empty?
    • The problem does not specify, so we should handle cases where either string is empty.

Strategy

  1. Generate Prefixes and Suffixes:
    • Generate all prefixes of s1.
    • Generate all suffixes of s2.
  2. Count Matching Prefix-Suffix Pairs:
    • Iterate over all prefixes of s1 and check if they appear as suffixes in s2.
    • Count and accumulate the number of matching pairs.
  3. Optimization Insight:
    • Store the prefixes and corresponding counts in a data structure like a HashMap.
    • Store the suffixes and corresponding counts in a similar manner.
    • Use these counts to quickly find and sum up matches.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int countPrefixSuffixPairs(String s1, String s2) {
        // Edge cases
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return 0;
        }

        // Maps to store the counts of prefixes and suffixes
        Map<String, Integer> prefixMap = new HashMap<>();
        Map<String, Integer> suffixMap = new HashMap<>();

        // Populate prefix map
        for (int i = 0; i < s1.length(); i++) {
            String prefix = s1.substring(0, i + 1);
            prefixMap.put(prefix, prefixMap.getOrDefault(prefix, 0) + 1);
        }

        // Populate suffix map
        for (int j = s2.length() - 1; j >= 0; j--) {
            String suffix = s2.substring(j);
            suffixMap.put(suffix, suffixMap.getOrDefault(suffix, 0) + 1);
        }

        // Count matching prefix-suffix pairs
        int count = 0;
        for (Map.Entry<String, Integer> entry : prefixMap.entrySet()) {
            String prefix = entry.getKey();
            if (suffixMap.containsKey(prefix)) {
                count += entry.getValue() * suffixMap.get(prefix);
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        
        String s1 = "abcde";
        String s2 = "cdeabc";
        
        System.out.println(solution.countPrefixSuffixPairs(s1, s2)); // Output: 3
    }
}

Time Complexity

  1. Prefix Generation:
    • Generating prefixes of s1 and suffixes of s2 both take O(n) where n is the length of the string.
    • There are indeed n prefixes and m suffixes for strings of length n and m respectively.
  2. HashMap Operations:
    • Inserting into and querying from a HashMap both take O(1) on average.
    • Hence, filling the maps take O(n) and O(m) respectively and checking for pairs takes O(n) in total.

Overall Complexity:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI