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;
}