C++UCS301
Complexity Lab C++ Setup Visualizer
Linear Data StructuresC++17

Strings & Processing

C++ strings are dynamic character sequences with safe size tracking and rich search, comparison, and transformation operations.

What to understand

  • std::string operations
  • Character frequencies
  • Palindromes and anagrams
  • Substring processing

Remember this

  1. 1Prefer std::string over raw C strings
  2. 2Use getline for spaces
  3. 3Index only within size()
  4. 4Many string problems reduce to counting or two pointers

Detailed notes

A string is an ordered character sequence, so many problems combine array techniques with character-specific operations. Common patterns include frequency tables, two pointers, sliding windows, and prefix-based matching.

std::string owns its memory, tracks length, and may contain any char value. Input with operator >> stops at whitespace, whereas getline reads an entire line. Character classification should receive unsigned-char values for fully safe portable code.

How it works

  1. 1Normalise case or character set only when the problem allows it.
  2. 2Choose counting, two pointers, or a window from the query.
  3. 3Define whether spaces and punctuation participate.
  4. 4Avoid copying substrings when indices or string_view suffice.

Where it is used

  • Text validation and parsing
  • Search boxes and tokenisation
  • DNA, logs, and protocol processing

Common mistakes

  • Confusing '\0' with the character '0'
  • Mixing getline with previous formatted input without consuming the newline
  • Quadratic concatenation or substring creation inside loops

Complexity analysis

OperationBestAverageWorstExtra space
Index accessO(1)O(1)O(1)O(1)
Find substringO(nm)O(nm)O(nm)O(1)
Append characterO(1)O(1) amortizedO(n)O(1)
Insert/deleteO(n)O(n)O(n)O(1)

C++ implementation

C++17 reference
main.cpp

Palindrome with two pointers

Two pointers compare mirrored characters in O(n) time without creating another string.

#include <cctype>
#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(const string& text) {
    int left = 0, right = static_cast<int>(text.size()) - 1;
    while (left < right) {
        while (left < right && !isalnum(text[left])) ++left;
        while (left < right && !isalnum(text[right])) --right;
        if (tolower(text[left]) != tolower(text[right])) return false;
        ++left;
        --right;
    }
    return true;
}

int main() {
    cout << boolalpha << isPalindrome("Never odd or even") << '\n';
}
20 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.

End-of-topic practice

Turn strings & processing into working C++.

The idea is fresh—use it now. Run visible cases, inspect failures, and then submit against hidden tests.

Browse the full arena
Practice 01Intermediate

Longest unique window

Find the length of the longest substring with no repeated character.

Target · O(n) expected Attempt in C++
Practice 02Foundation

Anagram check

Decide whether two lowercase strings contain exactly the same characters with the same frequencies.

Target · O(n) time, O(1) alphabet space Attempt in C++