educative.io

Why do we need to keep track of the counts of each char?

Courses
,
#1

Maybe, I am missing something. So feel free to correct me, but why do we need to keep track of the counts of each character? I implement my solutions in Go and came up with this:

func ContainsPermutation(str, pattern string) bool {
	charMap := make(map[byte]bool, len(pattern))
	for i := range pattern {
		charMap[pattern[i]] = true
	}

	i, count := 0, 0
	for i < len(str) {
		if _, exists := charMap[str[i]]; exists {
			count++
		} else {
			count = 0
		}

		if count == len(pattern) {
			return true
		}

		i++
	}

	return false
}
#2

i don’t know the GO language but my suggestion is to run your program against leetcode and see if it passes all test cases.

Educative problems are very good but cannot say if it has all the test cases to run and validate.

#3

In this solution you are only checking if the current character in the string exists in the pattern. With out tracking the count, you would give a false match for substrings with a subset of the characters of the pattern that happen to be the same length.

For example
pattern : “abcd”
string : “efgbbccef”
matched pattern : “bbcc”

image

We need to track to count as a permutation has to have the same character count as the pattern and not just a subset of character and be the same length.