Substring Problems

A substring is a contiguous range

A substring consists of consecutive characters. This is the main property that determines the algorithmic approach: it can be described by two boundaries, left and right, which can then be moved instead of enumerating every possible pair of boundaries.

Before solving the problem, it is useful to identify the shape of the constraint. If the fragment length is fixed, use a fixed-size window. If the window can grow until a condition is violated and then shrink from the left, a variable-size window often fits. If the solution depends on the last occurrence of a character, storing positions in a table or map is useful as well.

Example: the longest fragment without repetitions

Suppose we need the length of the longest substring in which characters do not repeat. We will store the last known position of each character. If the current character has already appeared inside the window, the left boundary can jump directly past its previous position.

Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0;
int best = 0;

for (int right = 0; right < text.length(); right++) {
    char c = text.charAt(right);

    if (lastSeen.containsKey(c)) {
        left = Math.max(left, lastSeen.get(c) + 1);
    }

    lastSeen.put(c, right);
    best = Math.max(best, right - left + 1);
}

The expression with Math.max is essential: the left boundary must not move backward because of an old occurrence that is already outside the current window. Each right position is visited once and left only moves forward, so with average O(1) access to HashMap, the solution runs in O(n).

Do not create a substring unless you need it

During the search, storing the boundaries and length of the best range is usually enough. If the problem requires the actual text, we can remember bestStart and create the substring once after the algorithm finishes. This avoids creating intermediate strings on every iteration.