C++UCS301
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.