Formatted question description: https://leetcode.ca/all/1794.html

1794. Count Pairs of Equal Substrings With Minimum Difference

Level

Medium

Description

You are given two strings firstString and secondString that are 0-indexed and consist only of lowercase English letters. Count the number of index quadruples (i,j,a,b) that satisfy the following conditions:

  • 0 <= i <= j < firstString.length
  • 0 <= a <= b < secondString.length
  • The substring of firstString that starts at the i-th character and ends at the j-th character (inclusive) is equal to the substring of secondString that starts at the a-th character and ends at the b-th character (inclusive).
  • j - a is the minimum possible value among all quadruples that satisfy the previous conditions.

Return the number of such quadruples.

Example 1:

Input: firstString = “abcd”, secondString = “bccda”

Output: 1

Explanation: The quadruple (0,0,4,4) is the only one that satisfies all the conditions and minimizes j - a.

Example 2:

Input: firstString = “ab”, secondString = “cd”

Output: 0

Explanation: There are no quadruples satisfying all the conditions.

Constraints:

  • 1 <= firstString.length, secondString.length <= 2 * 10^5
  • Both strings consist only of lowercase English letters.

Solution

First, find the minimum possible value j - a. If the equal substrings have lengths greater than 1, then after selecting shorter equal substrings, j - a can be reduced, so to obtain the minimum possible value j - a, always consider substrings with length 1. Find each character’s first occurrence in firstString and each character’s last occurrence in lastString, loop over all characters and find the minimum possible value j - a.

Next, count the number of pairs (j, a) that have the minimum possible value j - a. The number of pairs (j, a) is equal to the number of quadruples (i, j, a, b) since i == j and a == b.

Finally, return the count.

  • class Solution {
        public int countQuadruples(String firstString, String secondString) {
            Map<Character, Integer> map1 = new HashMap<Character, Integer>();
            Map<Character, Integer> map2 = new HashMap<Character, Integer>();
            int length1 = firstString.length(), length2 = secondString.length();
            for (int i = length1 - 1; i >= 0; i--) {
                char c = firstString.charAt(i);
                map1.put(c, i);
            }
            for (int i = 0; i < length2; i++) {
                char c = secondString.charAt(i);
                map2.put(c, i);
            }
            int minDifference = Integer.MAX_VALUE;
            Set<Character> keySet = map1.keySet();
            for (char c : keySet) {
                int index1 = map1.get(c);
                if (map2.containsKey(c)) {
                    int index2 = map2.get(c);
                    int difference = index1 - index2;
                    minDifference = Math.min(minDifference, difference);
                }
            }
            if (minDifference == Integer.MAX_VALUE)
                return 0;
            int quadruples = 0;
            for (char c : keySet) {
                int index1 = map1.get(c);
                if (map2.containsKey(c)) {
                    int index2 = map2.get(c);
                    int difference = index1 - index2;
                    if (difference == minDifference)
                        quadruples++;
                }
            }
            return quadruples;
        }
    }
    
  • Todo
    
  • print("Todo!")
    

All Problems

All Solutions