Bài toán

Link đến bài toán: 1759. Count Number of Homogenous Substrings

Phân tích

Bài này đơn giản, ta có thể dùng two pointer để giải quyết, hoặc nhanh hơn thì có thể dùng công thức cấp số cộng.

n * (n + 1) / 2

Ta dùng một biến đếm để đếm số lượng kí tự liên tiếp, nếu gặp kí tự khác thì tính số lượng substring có thể tạo ra từ số lượng kí tự liên tiếp đó, sau đó reset biến đếm.

Giải thuật

const MOD = 1e9 + 7

func countHomogenous(s string) int {
	res := 0
	streak := 0
	prevChar := int32(0)
	for _, c := range s {
		if prevChar != c {
			res = res + int(arithmeticProgression(streak)%MOD)
			streak = 1
			prevChar = c
		} else {
			streak += 1
		}
	}

	res = res + int(arithmeticProgression(streak)%MOD)

	return res
}

func arithmeticProgression(n int) int64 {
	return int64(0.5 * float64(n) * float64(1+n))
}