Substrings, subsequences, and character counts

Understand the idea

A substring is contiguous; a subsequence preserves order while allowing skips. Frequency counts discard order entirely. Choose the tool based on the exact relationship the problem asks for.

Work through an example

In 'abcde', 'bcd' is both; 'ace' is only a subsequence. 'abc' and 'bca' have equal counts but different order.

Time and space complexity

Counting O(n) time/O(σ) distinct keys; subsequence scan O(n+m).

Why it works

A subsequence pointer advances only on a matching text character.

Common mistakes

• Equal counts do not imply equal strings.
• A slice's upper endpoint is excluded.

Chapter lab · Python implementation

These examples operate on Python Unicode code points. A user-visible character can span several code points; normalization and grapheme segmentation need separate policies. The lab compares mirror positions without allocating a reversed copy. For every text problem, state whether case, punctuation, and whitespace matter.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def palindrome(text):
    left, right = 0, len(text)-1
    while left < right:
        if text[left] != text[right]:
            return False
        left += 1
        right -= 1
    return True

def frequencies(text):
    counts = {}
    for char in text:
        counts[char] = counts.get(char,0)+1
    return counts

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert palindrome('level') and palindrome('')
assert not palindrome('lever')
assert frequencies('abaca')=={'a':3,'b':1,'c':1}