Skip to content

1794. Count Pairs of Equal Substrings With Minimum Difference 👎

  • Time: O((|\texttt{classes}| + |\texttt{extraStudents}|) \log |\texttt{classes}|)
  • Space: $O(26) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  int countQuadruples(const string& s1, const string& s2) {
    // To minimize j - a, the length of the substring should be 1. This is
    // because for substrings with a size greater than 1, a will decrease,
    // causing j - a to become larger.
    int ans = 0;
    int diff = INT_MAX;  // diff := j - a
    vector<int> firstJ(26, -1);
    vector<int> lastA(26, -1);

    for (int j = s1.length() - 1; j >= 0; --j)
      firstJ[s1[j] - 'a'] = j;

    for (int a = 0; a < s2.length(); ++a)
      lastA[s2[a] - 'a'] = a;

    for (int i = 0; i < 26; ++i) {
      if (firstJ[i] == -1 || lastA[i] == -1)
        continue;
      if (firstJ[i] - lastA[i] < diff) {
        diff = firstJ[i] - lastA[i];
        ans = 0;
      }
      if (firstJ[i] - lastA[i] == diff)
        ++ans;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int countQuadruples(String s1, String s2) {
    // To minimize j - a, the length of the substring should be 1. This is
    // because for substrings with a size greater than 1, a will decrease,
    // causing j - a to become larger.
    int ans = 0;
    int diff = Integer.MAX_VALUE; // diff := j - a
    int[] firstJ = new int[26];
    int[] lastA = new int[26];
    Arrays.fill(firstJ, -1);
    Arrays.fill(lastA, -1);

    for (int j = s1.length() - 1; j >= 0; --j)
      firstJ[s1.charAt(j) - 'a'] = j;

    for (int a = 0; a < s2.length(); ++a)
      lastA[s2.charAt(a) - 'a'] = a;

    for (int i = 0; i < 26; ++i) {
      if (firstJ[i] == -1 || lastA[i] == -1)
        continue;
      if (firstJ[i] - lastA[i] < diff) {
        diff = firstJ[i] - lastA[i];
        ans = 0;
      }
      if (firstJ[i] - lastA[i] == diff)
        ++ans;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def countQuadruples(self, s1: str, s2: str) -> int:
    # To minimize j - a, the length of the substring should be 1. This is
    # because for substrings with a size greater than 1, a will decrease,
    # causing j - a to become larger.
    ans = 0
    diff = math.inf  # diff := j - a
    firstJ = {}
    lastA = {}

    for j in range(len(s1) - 1, -1, -1):
      firstJ[s1[j]] = j

    for a in range(len(s2)):
      lastA[s2[a]] = a

    for c in string.ascii_lowercase:
      if c not in firstJ or c not in lastA:
        continue
      if firstJ[c] - lastA[c] < diff:
        diff = firstJ[c] - lastA[c]
        ans = 0
      if firstJ[c] - lastA[c] == diff:
        ans += 1

    return ans