MARISSA MOLEJON | OCT2025-1 | Module-Complexity | Sprint 2 | Feat/improve with precomputing - #7

Summary

Speeds up both functions in improve_with_precomputing by precomputing
data once up front, avoiding redundant work per element.

Changes made

Design notes

find_longest_common_prefix relies on a property of sorted order: two
strings sharing a long common prefix are always adjacent (or separated
only by other strings sharing that same prefix) once sorted. This
guarantees the true maximum is found by checking only n-1 adjacent
pairs, instead of all n*(n-1)/2 pairs.

count_letters precomputes which lowercase letters appear anywhere in
the string in one pass, turning each subsequent "does this letter's
lowercase form appear in the string" check from an O(n) scan into an
O(1) set lookup.

Testing

All existing tests pass unchanged, including the large-input tests
(test_really_long_list, 1,000,000 strings; test_long_string,
10,000,000 characters).

Note: test_long_string's own setup code builds its input via repeated
string concatenation (s += next) in a loop, which is a known slow
pattern for building large strings and is unrelated to count_letters
itself - this made the test slow to run locally, but count_letters
was independently verified to run in under a second on an equivalent
10-million-character input built a different way.

Learning points

• "Precomputing" often means restructuring the problem so the expensive
  work happens once, up front, rather than being repeated per element -
  sorting once instead of comparing every pair is a strong example of
  this.
• A correctness argument (why adjacent pairs after sorting are
  sufficient) is as important as the complexity win itself - it's not
  enough for an optimization to be fast, it has to still be provably
  correct.
• Test setup code can itself be a performance bottleneck independent of
  the function under test - worth diagnosing which part is actually slow
  before assuming the implementation is at fault.

Checklist

• All tests pass, including large inputs
• No test files modified
• Self-reviewed for readability, naming, and correctness under scale