Question

1794. 统计距离最小的子串对个数

English Version

题目描述

输入数据为两个字符串firstString 和 secondString，两个字符串下标均从0开始，且均只包含小写的英文字符，请计算满足下列要求的下标四元组(i,j,a,b)的个数：

• 0 <= i <= j < firstString.length
• 0 <= a <= b < secondString.length
• firstString字符串中从i位置到j位置的子串(包括j位置的字符)和secondString字符串从a位置到b位置的子串(包括b位置字符)相等
• j-a的数值是所有符合前面三个条件的四元组中可能的最小值

返回符合上述 4 个条件的四元组的 个数 。

 

示例1：

输入：firstString = "abcd", secondString = "bccda"
输出：1
解释：(0,0,4,4)是唯一符合条件的四元组且其j-a的数值是最小的.

示例 2：

输入：firstString = "ab", secondString = "cd"
输出：0
解释：没有任何一个四元组能满足上述4个要求.

 

提示：

• 1 <= firstString.length, secondString.length <= 2 * 105
• 两个输入字符串均只包含小写英文字符.

解法

方法一：贪心 + 哈希表

题目实际上要我们找到一个最小的下标 $i$ 和一个最大的下标 $j$，使得 $firstString[i]$ 与 $secondString[j]$ 相等，且 $i - j$ 的值是所有满足条件的下标对中最小的。

因此，我们先用哈希表 $last$ 记录 $secondString$ 中每个字符最后一次出现的下标，然后遍历 $firstString$，对于每个字符 $c$，如果 $c$ 在 $secondString$ 中出现过，则计算 $i - last[c]$，如果 $i - last[c]$ 的值小于当前最小值，则更新最小值，同时更新答案为 1；如果 $i - last[c]$ 的值等于当前最小值，则答案加 1。

时间复杂度 $O(m + n)$，空间复杂度 $O(C)$。其中 $m$ 和 $n$ 分别是 $firstString$ 和 $secondString$ 的长度，而 $C$ 是字符集的大小。本题中 $C = 26$。

class Solution:
  def countQuadruples(self, firstString: str, secondString: str) -> int:
    last = {c: i for i, c in enumerate(secondString)}
    ans, mi = 0, inf
    for i, c in enumerate(firstString):
      if c in last:
        t = i - last[c]
        if mi > t:
          mi = t
          ans = 1
        elif mi == t:
          ans += 1
    return ans

class Solution {
  public int countQuadruples(String firstString, String secondString) {
    int[] last = new int[26];
    for (int i = 0; i < secondString.length(); ++i) {
      last[secondString.charAt(i) - 'a'] = i + 1;
    }
    int ans = 0, mi = 1 << 30;
    for (int i = 0; i < firstString.length(); ++i) {
      int j = last[firstString.charAt(i) - 'a'];
      if (j > 0) {
        int t = i - j;
        if (mi > t) {
          mi = t;
          ans = 1;
        } else if (mi == t) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int countQuadruples(string firstString, string secondString) {
    int last[26] = {0};
    for (int i = 0; i < secondString.size(); ++i) {
      last[secondString[i] - 'a'] = i + 1;
    }
    int ans = 0, mi = 1 << 30;
    for (int i = 0; i < firstString.size(); ++i) {
      int j = last[firstString[i] - 'a'];
      if (j) {
        int t = i - j;
        if (mi > t) {
          mi = t;
          ans = 1;
        } else if (mi == t) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

func countQuadruples(firstString string, secondString string) (ans int) {
  last := [26]int{}
  for i, c := range secondString {
    last[c-'a'] = i + 1
  }
  mi := 1 << 30
  for i, c := range firstString {
    j := last[c-'a']
    if j > 0 {
      t := i - j
      if mi > t {
        mi = t
        ans = 1
      } else if mi == t {
        ans++
      }
    }
  }
  return
}

function countQuadruples(firstString: string, secondString: string): number {
  const last: number[] = new Array(26).fill(0);
  for (let i = 0; i < secondString.length; ++i) {
    last[secondString.charCodeAt(i) - 97] = i + 1;
  }
  let [ans, mi] = [0, Infinity];
  for (let i = 0; i < firstString.length; ++i) {
    const j = last[firstString.charCodeAt(i) - 97];
    if (j) {
      const t = i - j;
      if (mi > t) {
        mi = t;
        ans = 1;
      } else if (mi === t) {
        ++ans;
      }
    }
  }
  return ans;
}