algoadvance

Leetcode 2744. Find Maximum Number of String Pairs

Problem Statement

You are given an array of strings words. Each string in words is a pair of lowercase English letters.

A pair of two different strings from words is a special substring if they have no common characters.

Return the maximum number of special substrings from the input array words.

Clarifying Questions

  1. Input Constraints:
    • Can there be duplicate words in the input array?
    • What is the maximum length of the input array words?
  2. Output Specification:
    • Should each pair be counted once or multiple times if they appear multiple times in the input array?

Example

Input: words = ["ab", "bc", "cd", "de"]
Output: 2

Strategy

  1. Identify Unique Pairs: Iterate over all possible pairs of strings in the array and check if they are special substrings.
  2. No Common Characters Check: Use a set to check for common characters between pairs efficiently.

Code

import java.util.HashSet;
import java.util.Set;

public class MaximumStringPairs {

    public int maxSpecialSubstrings(String[] words) {
        int maxPairs = 0;

        for (int i = 0; i < words.length - 1; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (noCommonCharacters(words[i], words[j])) {
                    maxPairs++;
                }
            }
        }

        return maxPairs;
    }

    private boolean noCommonCharacters(String word1, String word2) {
        Set<Character> charsInWord1 = new HashSet<>();
        for (char c : word1.toCharArray()) {
            charsInWord1.add(c);
        }

        for (char c : word2.toCharArray()) {
            if (charsInWord1.contains(c)) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        MaximumStringPairs solution = new MaximumStringPairs();
        String[] words = {"ab", "bc", "cd", "de"};
        System.out.println(solution.maxSpecialSubstrings(words));  // Output: 2
    }
}

Time Complexity

The time complexity of the solution can be analyzed as follows:

  1. Outer Loop: Iterates over words.length - 1.
  2. Inner Loop: Iterates over the remaining elements after the current element in the outer loop.
  3. Common Character Check: Comparing two words for common characters takes O(1) since each word has a fixed length of 2, and the set operations are in constant time.

Thus, the overall time complexity is O(n^2), where n is the length of the words array.

This solution ensures that all possible pairs are checked optimally without additional space complexity considerations beyond the fixed-length input strings.

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