Strings

Strings are the most common input you'll process: log lines, user input, file paths, tokens. String problems also introduce three patterns you'll use everywhere — frequency counting, the sliding window, and smart pattern matching.

A string is an array of characters, so everything from Module 1 applies: O(1) access by index, two pointers, in-place tricks (on a mutable copy).

Frequency counting. Many questions ("is this an anagram?", "first unique character?") reduce to counting how often each character appears. Use a map, or a fixed [26]int when the alphabet is known and small.

The sliding window. For "longest/shortest substring such that…", keep a window [left, right]. Grow right one step at a time; when the window breaks the rule, advance left until it's valid again. Each index enters and leaves once, so it's O(n) instead of checking every substring in O(n²).

Pattern search. The naive approach tries every start position and compares — O(n·m). KMP (Knuth–Morris–Pratt) precomputes, for each prefix of the pattern, the longest proper prefix that's also a suffix. On a mismatch it uses that table to skip ahead without ever moving backwards in the text: O(n + m).

• Strings are immutable byte sequences, conventionally UTF-8. To edit one, convert to []byte or []rune, change that, and convert back.
• len(s) counts bytes. len("héllo") is 6, because é takes two bytes. utf8.RuneCountInString counts characters.
• s[i] is a byte; range gives runes. for i, r := range s decodes UTF-8 for you, and i is the byte offset where that rune starts.
• []rune(s) gives you O(1) indexing by character at the cost of an O(n) conversion and 4 bytes per character.
• Build strings with strings.Builder. Repeated += copies the whole string every time.
• The strings package (Fields, Split, Index, EqualFold…) and unicode package (IsLetter, ToLower) cover most needs. Exercises ask you to hand-roll a few so you know what they cost.

Longest substring with at most k distinct characters — not one of your exercises, but the same shape as LongestUniqueSubstring:

func longestAtMostK(s string, k int) int {
	r := []rune(s)
	count := map[rune]int{}
	best, left := 0, 0
	for right, ch := range r {
		count[ch]++                 // 1. grow the window
		for len(count) > k {         // 2. shrink until valid
			count[r[left]]--
			if count[r[left]] == 0 {
				delete(count, r[left])
			}
			left++
		}
		best = max(best, right-left+1) // 3. record the answer
	}
	return best
}

Grow, shrink until valid, record. Most window problems differ only in what "valid" means.

• Frequency map — anagrams, permutations, "first unique", "most common".
• Sliding window — longest/shortest substring with some property.
• Two pointers — palindromes, reversing words.
• Prefix function (KMP) — repeated searches, finding periods, "shortest palindrome".

Nine functions in exercises.go, roughly easiest first. Several tests use accented or non-Latin characters on purpose — if you index bytes where you meant runes, they'll catch it.

go test ./02-strings/

Do IndexOf before PrefixFunction and KMPSearch so you feel the difference. For KMP, work through pi for "ababaca" on paper first.

The files for this module

Everything below is also in the course download, in 02-strings/. Work in exercises.go; the tests decide when you’re done.

// Package strs is Module 2: strings. (Named strs so it doesn't shadow the
// standard library's strings package, which you're free to use.)
//
// Go strings are immutable byte sequences, usually UTF-8. Indexing s[i]
// gives a byte; ranging `for i, r := range s` gives runes (code points) and
// their byte offsets. Several exercises below care about the difference.
package strs

//go:build !solutions

package strs

// ReverseString reverses s by runes, not bytes, so multi-byte characters
// survive: "héllo" -> "olléh". Target: O(n).
func ReverseString(s string) string {
	// TODO
	return ""
}

// IsPalindrome reports whether s reads the same both ways, considering only
// letters and digits and ignoring case. "A man, a plan, a canal: Panama"
// -> true. Use the unicode package. Target: O(n).
func IsPalindrome(s string) bool {
	// TODO
	return false
}

// ReverseWords reverses the order of words and collapses runs of spaces:
// "  the sky  is blue " -> "blue is sky the". Target: O(n).
func ReverseWords(s string) string {
	// TODO
	return ""
}

// IsAnagram reports whether b is a rearrangement of a's runes.
// "listen", "silent" -> true. Pattern: frequency counting. Target: O(n).
func IsAnagram(a, b string) bool {
	// TODO
	return false
}

// Compress run-length encodes s, writing the count only when it's above 1:
// "aaabccdddd" -> "a3bc2d4". Build the result with strings.Builder rather
// than += in a loop. Target: O(n).
func Compress(s string) string {
	// TODO
	return ""
}

// LongestUniqueSubstring returns the length (in runes) of the longest
// substring with no repeated character. "abcabcbb" -> 3 ("abc").
// Pattern: sliding window + map of last-seen positions. Target: O(n).
func LongestUniqueSubstring(s string) int {
	// TODO
	return 0
}

// IndexOf returns the byte index of the first occurrence of pattern in
// text, or -1. An empty pattern matches at 0. Do it by hand (naive scan) —
// no strings.Index. Target: O(n·m).
func IndexOf(text, pattern string) int {
	// TODO
	return -1
}

// PrefixFunction returns the KMP failure table for p: pi[i] is the length
// of the longest proper prefix of p[:i+1] that is also a suffix of it.
// "ababaca" -> [0 0 1 2 3 0 1]. Target: O(m).
func PrefixFunction(p string) []int {
	// TODO
	return nil
}

// KMPSearch returns the byte index of every (possibly overlapping)
// occurrence of pattern in text, using PrefixFunction. Returns nil for an
// empty pattern or no matches. "aaaa", "aa" -> [0 1 2]. Target: O(n+m).
func KMPSearch(text, pattern string) []int {
	// TODO
	return nil
}

package strs

import (
	"slices"
	"testing"
)

func TestReverseString(t *testing.T) {
	for _, tc := range []struct{ in, want string }{
		{"hello", "olleh"},
		{"héllo", "olléh"},
		{"Go→Rust", "tsuR→oG"},
		{"", ""},
	} {
		if got := ReverseString(tc.in); got != tc.want {
			t.Errorf("ReverseString(%q) = %q, want %q", tc.in, got, tc.want)
		}
	}
}

func TestIsPalindrome(t *testing.T) {
	for _, tc := range []struct {
		in   string
		want bool
	}{
		{"A man, a plan, a canal: Panama", true},
		{"race a car", false},
		{"No 'x' in Nixon", true},
		{"Ésé", true},
		{"ab", false},
		{"", true},
	} {
		if got := IsPalindrome(tc.in); got != tc.want {
			t.Errorf("IsPalindrome(%q) = %v, want %v", tc.in, got, tc.want)
		}
	}
}

func TestReverseWords(t *testing.T) {
	for _, tc := range []struct{ in, want string }{
		{"the sky is blue", "blue is sky the"},
		{"  hello world  ", "world hello"},
		{"a good   example", "example good a"},
		{"one", "one"},
	} {
		if got := ReverseWords(tc.in); got != tc.want {
			t.Errorf("ReverseWords(%q) = %q, want %q", tc.in, got, tc.want)
		}
	}
}

func TestIsAnagram(t *testing.T) {
	for _, tc := range []struct {
		a, b string
		want bool
	}{
		{"listen", "silent", true},
		{"anagram", "nagaram", true},
		{"rat", "car", false},
		{"ab", "abb", false},
		{"über", "rübe", true},
	} {
		if got := IsAnagram(tc.a, tc.b); got != tc.want {
			t.Errorf("IsAnagram(%q, %q) = %v, want %v", tc.a, tc.b, got, tc.want)
		}
	}
}

func TestCompress(t *testing.T) {
	for _, tc := range []struct{ in, want string }{
		{"aaabccdddd", "a3bc2d4"},
		{"abc", "abc"},
		{"zzzzzzzzzzzz", "z12"},
		{"ééa", "é2a"},
		{"", ""},
	} {
		if got := Compress(tc.in); got != tc.want {
			t.Errorf("Compress(%q) = %q, want %q", tc.in, got, tc.want)
		}
	}
}

func TestLongestUniqueSubstring(t *testing.T) {
	for _, tc := range []struct {
		in   string
		want int
	}{
		{"abcabcbb", 3},
		{"bbbbb", 1},
		{"pwwkew", 3},
		{"abba", 2},
		{"", 0},
		{"日本日本語", 3},
	} {
		if got := LongestUniqueSubstring(tc.in); got != tc.want {
			t.Errorf("LongestUniqueSubstring(%q) = %d, want %d", tc.in, got, tc.want)
		}
	}
}

func TestIndexOf(t *testing.T) {
	for _, tc := range []struct {
		text, pat string
		want      int
	}{
		{"hello world", "world", 6},
		{"aaab", "ab", 2},
		{"abc", "d", -1},
		{"abc", "", 0},
		{"ab", "abc", -1},
	} {
		if got := IndexOf(tc.text, tc.pat); got != tc.want {
			t.Errorf("IndexOf(%q, %q) = %d, want %d", tc.text, tc.pat, got, tc.want)
		}
	}
}

func TestPrefixFunction(t *testing.T) {
	for _, tc := range []struct {
		in   string
		want []int
	}{
		{"ababaca", []int{0, 0, 1, 2, 3, 0, 1}},
		{"aaaa", []int{0, 1, 2, 3}},
		{"abcd", []int{0, 0, 0, 0}},
	} {
		if got := PrefixFunction(tc.in); !slices.Equal(got, tc.want) {
			t.Errorf("PrefixFunction(%q) = %v, want %v", tc.in, got, tc.want)
		}
	}
}

func TestKMPSearch(t *testing.T) {
	for _, tc := range []struct {
		text, pat string
		want      []int
	}{
		{"aaaa", "aa", []int{0, 1, 2}},
		{"abababab", "abab", []int{0, 2, 4}},
		{"the cat sat on the mat", "the", []int{0, 15}},
		{"abc", "z", nil},
		{"abc", "", nil},
	} {
		if got := KMPSearch(tc.text, tc.pat); !slices.Equal(got, tc.want) {
			t.Errorf("KMPSearch(%q, %q) = %v, want %v", tc.text, tc.pat, got, tc.want)
		}
	}
}

//go:build solutions

package strs

import (
	"strconv"
	"strings"
	"unicode"
)

func ReverseString(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

func IsPalindrome(s string) bool {
	var clean []rune
	for _, r := range s {
		if unicode.IsLetter(r) || unicode.IsDigit(r) {
			clean = append(clean, unicode.ToLower(r))
		}
	}
	for i, j := 0, len(clean)-1; i < j; i, j = i+1, j-1 {
		if clean[i] != clean[j] {
			return false
		}
	}
	return true
}

func ReverseWords(s string) string {
	words := strings.Fields(s)
	for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
		words[i], words[j] = words[j], words[i]
	}
	return strings.Join(words, " ")
}

func IsAnagram(a, b string) bool {
	counts := make(map[rune]int)
	for _, r := range a {
		counts[r]++
	}
	for _, r := range b {
		counts[r]--
		if counts[r] < 0 {
			return false
		}
	}
	for _, c := range counts {
		if c != 0 {
			return false
		}
	}
	return true
}

func Compress(s string) string {
	r := []rune(s)
	var b strings.Builder
	for i := 0; i < len(r); {
		j := i
		for j < len(r) && r[j] == r[i] {
			j++
		}
		b.WriteRune(r[i])
		if n := j - i; n > 1 {
			b.WriteString(strconv.Itoa(n))
		}
		i = j
	}
	return b.String()
}

func LongestUniqueSubstring(s string) int {
	last := make(map[rune]int) // rune -> last index (in rune positions)
	best, start := 0, 0
	for i, r := range []rune(s) {
		if prev, ok := last[r]; ok && prev >= start {
			start = prev + 1
		}
		last[r] = i
		best = max(best, i-start+1)
	}
	return best
}

func IndexOf(text, pattern string) int {
	n, m := len(text), len(pattern)
	for i := 0; i+m <= n; i++ {
		if text[i:i+m] == pattern {
			return i
		}
	}
	return -1
}

func PrefixFunction(p string) []int {
	pi := make([]int, len(p))
	k := 0
	for i := 1; i < len(p); i++ {
		for k > 0 && p[i] != p[k] {
			k = pi[k-1]
		}
		if p[i] == p[k] {
			k++
		}
		pi[i] = k
	}
	return pi
}

func KMPSearch(text, pattern string) []int {
	if pattern == "" {
		return nil
	}
	pi := PrefixFunction(pattern)
	var out []int
	k := 0
	for i := 0; i < len(text); i++ {
		for k > 0 && text[i] != pattern[k] {
			k = pi[k-1]
		}
		if text[i] == pattern[k] {
			k++
		}
		if k == len(pattern) {
			out = append(out, i-k+1)
			k = pi[k-1]
		}
	}
	return out
}

• Benchmark your IndexOf against strings.Index on a long text. (The standard library uses tricks like Rabin–Karp and SIMD.)
• LeetCode practice: Minimum Window Substring, Longest Palindromic Substring, Find All Anagrams in a String.

Four questions. Answer each one in your head — or out loud — before you open the answer.

Commit your work before you move on to module 3, so git log shows your own progress through the course.