Strings for DSA

C++ std::string behaves like a mutable char sequence. DSA string problems use two pointers, sliding window, prefix counts, and sometimes KMP for pattern matching.

Useful operations

• s[i] — O(1) access
• s.size(), substring s.substr(pos, len)
• Compare lexicographically with <

Palindrome check (two pointers)

#include 
#include 

int main() {
    std::string s = "level";
    int lo = 0, hi = (int)s.size() - 1;
    bool ok = true;
    while (lo < hi) {
        if (s[lo++] != s[hi--]) { ok = false; break; }
    }
    std::cout << (ok ? "palindrome\n" : "not\n");
    return 0;
}

Character counts

Fixed alphabet (26 letters) → array of counts O(n). Unicode-heavy text may need hash map.

Important interview questions and answers

1. Q: String vs char array?
   A: std::string manages length and allocation; C string ends at '\0'.
2. Q: Substring complexity?
   A: substr may copy O(k) characters—two pointers avoid extra copies in many problems.

Self-check

1. How check palindrome in O(n) time?
2. When use array of 26 counts vs hash map?

Tip: Two pointers from both ends solve many palindrome and pair problems in O(n).