count_contained_permutations

README

Count Contained Permutations

You're given two non-empty strings: a big string and a small string. Write a function that returns the number of permutations of the small string that are contained in the big string.

Repeated permutations should be counted, and the small string counts as a permutation of itself.

Sample Input

bigString = "cbabcacabca"
smallString = "abc"

Sample Output

6 // "cba", "abc", "bca", "cab", "abc", "bca"

Documentation

Index

• func CountContainedPermutations(bigString, smallString string) int
• type Trie
  • func NewTrie() Trie
  • func (t Trie) Add(str string, i int)
  • func (t Trie) AddSlice(slice []string)

Functions

func CountContainedPermutations

func CountContainedPermutations(bigString, smallString string) int

CountContainedPermutations O(b + s) time | O(s) space - where b is the length of the big input string and s is the length of the small input string

Types

type Trie

type Trie struct {
	// contains filtered or unexported fields
}

func NewTrie

func NewTrie() Trie

func (Trie) Add

func (t Trie) Add(str string, i int)

func (Trie) AddSlice

func (t Trie) AddSlice(slice []string)