leetcode-go/hard/420.strong-password-checker.go

func strongPasswordChecker(s string) int {
	// Missing: insert/delete/replace
	// Too short: insert
	// Too long: delete
	// Repeat: insert/delete/replace
	n := len(s)
	if n == 0 {
		return 6
	}
	a, A, d, cnt := 1, 1, 1, 0 // Find the cnt of missing and repeat
	repeat := make([]int, 0)
	pre := rune(s[0])
	for _, r := range s {
		if 'a' <= r && r <= 'z' {
			a = 0
		} else if 'A' <= r && r <= 'Z' {
			A = 0
		} else if '0' <= r && r <= '9' {
			d = 0
		}
		if r == pre {
			cnt++
		} else {
			if 3 <= cnt {
				repeat = append(repeat, cnt)
			}
			cnt = 1
			pre = r
		}
	}
	if 3 <= cnt {
		repeat = append(repeat, cnt)
	}
	miss := a + A + d
	if n < 6 {
		return miss + maxInt(0, 6-n-miss) // Repeat && missing can be both solved by insert
	}
	exceed, replace, m := maxInt(0, n-20), 0, len(repeat)
	res := exceed
	for k := 1; k <= 2; k++ { // Smaller k first, cauz aaa -> aa: 1 step, aaaa -> xaa: 2 step
		for i := 0; i < m && 0 < exceed; i++ {
			if repeat[i] < 3 || repeat[i]%3 != k-1 {
				continue
			}
			dec := minInt(exceed, k)
			repeat[i], exceed = repeat[i]-dec, exceed-dec
		}
	}
	for i := 0; i < m; i++ {
		if 3 <= repeat[i] && 0 < exceed {
			dec := minInt(exceed, repeat[i]-2) // 3k+2 -> 2 to make exceed == 0
			repeat[i], exceed = repeat[i]-dec, exceed-dec
		}
		if 3 <= repeat[i] {
			replace += repeat[i] / 3
		}
	}
	return res + maxInt(miss, replace)
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}