Growing outward from a center

Two problems where the obvious table is beaten by something simpler.

Why it works

There are two kinds of center

An odd-length stretch centers on a character. An even-length one centers between two characters. A string of length n therefore has 2n minus 1 possible centers, and missing the even ones is the classic error.

The usual shape runs one expansion per character and one per gap, or equivalently loops over all 2n minus 1 centers and derives the two starting indexes arithmetically.

1text = "aabaa"2left = right = 2                 # centered on the b3 4while left >= 0 and right < len(text) and text[left] == text[right]:5    print("found:", text[left:right + 1])6    left -= 17    right += 18 9print("stopped with left =", left, "and right =", right)

One expansion from one center produced three answers, and it stopped by running off both ends at once.

Predict the output· 5 min

Predict the output: only odd centers

This expands from character centers only and never from the gaps between them. Type the two values it prints.

Python

1def count_odd_only(text):2    total = 03    def expand(left, right):4        found = 05        while left >= 0 and right < len(text) and text[left] == text[right]:6            found += 17            left -= 18            right += 19        return found10    for center in range(len(text)):11        total += expand(center, center)12    return total13 14print(count_odd_only("aaa"), count_odd_only("abba"))

Printed output

Problem· 25 min

Palindromic Substrings

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 25 min

Longest Palindromic Substring

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1text = "aabaa"2left = right = 2 # centered on the b3 4while left >= 0 and right < len(text) and text[left] == text[right]:5 print("found:", text[left:right + 1])6 left -= 17 right += 18 9print("stopped with left =", left, "and right =", right)

1def count_odd_only(text):2 total = 03 def expand(left, right):4 found = 05 while left >= 0 and right < len(text) and text[left] == text[right]:6 found += 17 left -= 18 right += 19 return found10 for center in range(len(text)):11 total += expand(center, center)12 return total13 14print(count_odd_only("aaa"), count_odd_only("abba"))