Strings

Why strings matter in algorithms

A string looks like ordinary text, but in algorithmic problems it is useful to view it as a sequence of characters with indexes. This lets us apply familiar ideas: traverse the string from left to right, count elements, move two pointers, and maintain the boundaries of the current fragment.

The main feature of string problems is that the result often depends not only on the characters themselves, but also on their order and positions. The same set of letters may therefore require very different approaches depending on whether we are looking for frequencies, symmetry, or a contiguous part of the string.

What this section covers

• String Basics. We will look at strings from an algorithmic perspective: indexes, traversal, immutability, and the cost of common actions.
• Character Counting. You will learn to store character frequencies and choose between a counter array and an associative structure.
• Two Pointers. We will transfer the familiar technique to strings and process data from both ends without unnecessary passes.
• Sliding Window. We will work with a contiguous fragment of a string whose boundaries move as characters are processed.
• Palindromes. You will learn to recognize strings and ranges that read the same from both directions.
• Anagrams. We will see how to compare strings by their character composition when order does not matter.
• Substring Problems. We will combine the previous techniques and learn to choose an approach for problems about contiguous parts of a string.

A string as a space for an algorithm

String word = "algorithm";

for (int i = 0; i < word.length(); i++) {
    char current = word.charAt(i);
    System.out.println(current);
}

Here we simply move through the string by index. In the following topics, these same indexes will become window boundaries, two pointers, or positions that let us make quick decisions about the current fragment.