LC828.统计子串中的唯一字符

题目

link

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

例如： s = "LEETCODE" ，则其中 "L", "T", "C", "O", "D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

示例 1：

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

示例 2：

输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。

示例 3：

输入：s = "LEETCODE"
输出：92

提示：

1 <= s.length <= 10^5
s 只包含大写英文字

解答

是一道非常经典的乘法原理的题目，可以当做模板题
对于每一个字符 s[i]，我们考虑 s[i] 对于全局的贡献。统计以 s[i] 为 唯一字符 的字符串个数，就等于得到了 s[i] 对于全局的贡献。
那么，问题转化为，如何获取以 s[i] 为 唯一字符 的字符串个数。合法字符串个数 = 合法左端点个数乘以合法右端点个数。那么合法左端点个数如何获取？
假定当前字符下标为 i ，左边最近的相同字符下标为 k（我们假定左边一定有相同字符，后面单独讨论如果没有），那么 合法左端点 的个数，就是 k - i。同理可以得到 合法右端点 的个数。二者相乘就是当前字符对于全局的贡献。
如果左侧不存在和 s[i] 相同的字符怎么办？那么就将左侧最近相同字符出现的位置记为 -1,那么 合法左端点 的个数就是 i + 1 ,这个也是合理的。

[!attention]
对于下标从 0 开始的数组而言，下标为 index，就说明其前面一共有 index 个数字

i + 1 就说明，s[i] 前面所有的字符，加上 s[i] 自己，都可以成为 合法左端点，因此这种想法是合理的。对于右侧而言，如果无法找到右侧最近的相同字符，就可以将数值 sLength 记为右侧最近相同字符的下标。
具体关系如下图所示。

此题和 907. 子数组的最小值之和 是高度相似的，但是难度上进行了削弱，不再利用单调栈知识了。[[../../栈和队列/单调栈/下一个更大数字/LC907.子数组的最小值之和|LC907.子数组的最小值之和]]

代码

// Created by Albert at 2023/06/29 10:59
// leetgo: 1.3.2
// https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/

package main

import (
	"fmt"

	. "github.com/j178/leetgo/testutils/go"
)

// @lc code=begin

func uniqueLetterString(s string) int {
	// recordLeft[s[i]]: the index of the first char the same as s[i](left)
	// recordRight[s[i]]: the index of the first char the same as s[i](right)
	// recordIndex[s[i]]: record the index to supply data for recrodLeft and recordRight

	sLength := len(s)
	recordLeft := make([]int, sLength)
	recordRight := make([]int, sLength)
	recordIndex := make([]int, 26)

	// record Left
	for i := range recordIndex {
		recordIndex[i] = -1
	}

	for i := 0; i < sLength; i += 1 {
		currentCharCode := int(s[i] - 'A')
		// from recordIndex[] get the first left index
		recordLeft[i] = recordIndex[currentCharCode]
		// fill current index to recordIndex[]
		recordIndex[currentCharCode] = i
	}

	// record Right
	for i := range recordIndex {
		recordIndex[i] = sLength
	}

	for i := sLength - 1; i >= 0; i -= 1 {
		currentCharCode := int(s[i] - 'A')
		recordRight[i] = recordIndex[currentCharCode]
		recordIndex[currentCharCode] = i
	}

	ans := 0
	for i := 0; i < sLength; i++ {
		// possible value of LEFT endpoint: (i - recordLeft[i])
		// possible value of RIGHT endpoint: (recordRight[i] - i)
		ans += (i - recordLeft[i]) * (recordRight[i] - i)
	}
	return ans
}

// @lc code=end

func main() {
	// stdin := bufio.NewReader(os.Stdin)
	// s := Deserialize[string](ReadLine(stdin))

	s := "ABC"
	ans := uniqueLetterString(s)

	fmt.Println("\noutput:", Serialize(ans))
}

LC828.统计子串中的唯一字符 ​

题目 ​

解答 ​

代码 ​

LC828.统计子串中的唯一字符

题目

解答

代码