CodeWithYash

Foundation · Module 6 · Lesson 5

Palindrome & partitioning

Compare ends or maintain regions.

15–25 min readLesson 36 of 123

Lesson 36 of 123

1d streak

Theory lesson · Step-by-step

Understand Palindrome & partitioning

Compare ends or maintain regions.

Worked approach

Trace the reasoning step by step

  1. 1Assign a precise meaning to both pointers in Palindrome & partitioning.
  2. 2Use ordering or a read/write contract to decide which pointer can move safely.
  3. 3Record a match or write a finalized value before moving past it.
  4. 4Move at least one pointer monotonically on every iteration.
  5. 5Test duplicates, crossing pointers, empty ranges, and all-equal values.

Concrete example

Check whether "racecar" is a palindrome.

  1. 1Compare r/r, a/a, and c/c from the ends.
  2. 2Pointers meet at e.

Every mirrored pair matches, so the string is a palindrome.

What must remain true (Loop Invariant)

The region discarded by Palindrome & partitioning cannot contain an unexamined valid answer; each pointer move is justified by order or a finalized output position.

Cost Model

Complexity & Trade-offs

Two-end scan
O(n)
O(1)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Sorted pair search, compaction, merging, partitioning, and palindrome checks.
  • Replacing nested loops when boundaries move monotonically.
  • Maintaining disjoint processed and candidate regions.

Common mistakes

  • Moving a pointer without proving the discarded region is impossible.
  • Forgetting duplicate skipping in enumeration problems.
  • Applying an order-dependent pointer rule to unsorted data.

Practice prompts

  • Reproduce the worked Palindrome & partitioning example without looking at the trace.
  • Change one input condition and explain whether the Palindrome & partitioning invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.