String Problems in Contests

Real-world analogy

What is it?

String problems in competitive programming involve manipulating and analyzing text data. Common tasks include checking palindromes, reversing strings, counting character frequencies, finding anagrams, and extracting substrings. These are among the most popular problem types in beginner contests.

Real-world relevance

DNA sequences in biology are analyzed as strings of A, T, G, C — scientists check for palindromic sequences that are important for gene editing. Spell checkers look for anagrams and similar words. Search engines break text into substrings to find matches. String algorithms power the internet!

Key points

• Palindrome Check — A palindrome reads the same forwards and backwards, like 'racecar' or 'madam'. To check: compare s[0] with s[n-1], s[1] with s[n-2], etc. If all pairs match, it is a palindrome. A simpler way: reverse the string and check if it equals the original. In C++: string rev = s; reverse(rev.begin(), rev.end()); return s == rev;
• Reversing a String — To reverse a string, you can use the built-in reverse(s.begin(), s.end()) function which reverses in place. Or do it manually: swap characters from both ends moving inward — swap s[0] with s[n-1], s[1] with s[n-2], etc. You can also build a new reversed string by looping from the end to the beginning.
• Counting Vowels and Consonants — A very common problem pattern: loop through the string, convert each character to lowercase, then check if it is a, e, i, o, or u. One clean way: create a string vowels = "aeiou" and use vowels.find(c) != string::npos. Count everything else (that is a letter) as a consonant.
• Frequency Counting with Arrays — To count how often each letter appears, create an array freq[26] = {0}. For each character c, do freq[c - 'a']++. This maps 'a' to index 0, 'b' to index 1, etc. This technique is used in tons of CP problems — anagram checking, finding the most common letter, checking if two strings have the same letters.
• Checking for Anagrams — Two strings are anagrams if they have the same letters in different order — like 'listen' and 'silent'. Method 1: sort both strings and compare. Method 2: count letter frequencies for both and compare the frequency arrays. Method 2 is faster (O(n) vs O(n log n)).
• Substrings — s.substr(start, length) extracts a piece of the string. s.substr(2, 3) takes 3 characters starting at index 2. s.find("abc") returns the position where 'abc' first appears (or string::npos if not found). These are essential for pattern matching problems in CP.
• Common Contest Patterns — String problems you will see over and over: (1) Count characters matching a condition. (2) Transform the string (flip case, remove vowels, etc.). (3) Check a property (palindrome, balanced brackets). (4) Compare two strings. (5) Build a new string from an old one. Master these five patterns and you can solve most beginner string problems!

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    
    // 1. Check if palindrome
    string rev = s;
    reverse(rev.begin(), rev.end());
    if (s == rev) {
        cout << s << " is a palindrome!" << endl;
    } else {
        cout << s << " is NOT a palindrome." << endl;
    }
    
    // 2. Count vowels
    int vowels = 0;
    string vowelList = "aeiouAEIOU";
    for (char c : s) {
        if (vowelList.find(c) != string::npos) {
            vowels++;
        }
    }
    cout << "Vowels: " << vowels << endl;
    
    // 3. Frequency count
    int freq[26] = {0};
    for (char c : s) {
        if (isalpha(c)) {
            freq[tolower(c) - 'a']++;
        }
    }
    
    // Print most common letter
    int maxFreq = 0;
    char maxChar = 'a';
    for (int i = 0; i < 26; i++) {
        if (freq[i] > maxFreq) {
            maxFreq = freq[i];
            maxChar = 'a' + i;
        }
    }
    cout << "Most common letter: " << maxChar << " (" << maxFreq << " times)" << endl;
    
    return 0;
}
// Input:  racecar
// Output: racecar is a palindrome!
//         Vowels: 3
//         Most common letter: r (2 times)

Line-by-line walkthrough

1. 1. We read a word into string s.
2. 2. To check for palindrome: we make a copy, reverse it, and compare with the original.
3. 3. reverse(s.begin(), s.end()) is a built-in function that reverses a string in place.
4. 4. For counting vowels, we check if each character exists in our vowelList string.
5. 5. string::npos means 'not found' — so if find() does NOT return npos, the character IS a vowel.
6. 6. For frequency counting, we create an array of 26 zeros (one for each letter).
7. 7. freq[tolower(c) - 'a']++ maps each letter to an index (a=0, b=1, ..., z=25) and counts it.
8. 8. Finally, we scan the frequency array to find which letter appeared the most.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    
    // Check if palindrome
    bool isPalin = true;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] != s[s.length() - i]) {
            isPalin = false;
            break;
        }
    }
    
    if (isPalin) cout << "Palindrome!" << endl;
    else cout << "Not a palindrome." << endl;
    
    return 0;
}
// Input: racecar
// Expected: Palindrome!
// Actual: Might crash or give wrong answer

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• String Problems for CP — Complete Guide (Luv)
• String Algorithms — CP-Algorithms (CP-Algorithms)
• String Contest Problems (Codeforces)