ReviseAlgo Logo

Arrays and Strings

String Operations

Common string manipulation techniques for real-world and interview problems

Interview: String manipulation is among the most common interview topics — reversals, parsing, searching, and building are tested constantly

String Operations

std::string provides a comprehensive API for common manipulations. Knowing the right operation and its complexity separates clean, efficient interview code from brute-force solutions. The most important operations to internalize are: find, substr, insert, erase, replace, and conversion functions.

Searching and Finding

find() returns the starting position of a substring, or std::string::npos (a large value, typically SIZE_MAX) if not found. Always compare against string::npos using the returned size_t type — comparing against -1 (signed) can silently fail. Variants include rfind (search from end), find_first_of (any char from a set), and find_first_not_of (first char not in a set — used for trimming).

Splitting Strings

std::string has no built-in split. The idiomatic approaches: (1) std::istringstream with operator>> splits on whitespace, (2) a loop with find(delim) and substr splits on any delimiter, (3) C++20 ranges-based split view avoids copies entirely.

Number Conversions

C++11 provides stoi, stol, stoll, stof, stod for string-to-number, and to_string() for number-to-string. These throw std::invalid_argument on invalid input and std::out_of_range on overflow. For high-performance parsing, C++17's std::from_chars is locale-independent and allocation-free.

Building Strings Efficiently

Building a string by concatenating in a loop with + creates O(n²) temporary objects. Use += (amortized O(1) per append), or std::ostringstream for formatted output, or pre-reserve() when the final size is known.

Interview Corner

Q: What is the time complexity of reverse a string, and how do you do it in-place?

A: Reversing is O(n) and O(1) space. Use std::reverse(s.begin(), s.end()). Internally: swap characters from both ends moving inward until pointers meet. For interview, you can implement it as: int l=0, r=s.size()-1; while(l<r) swap(s[l++], s[r--]);

Q: How do you check if a string is a palindrome efficiently?

A: Two-pointer approach: compare characters from both ends. O(n) time, O(1) space. bool isPalin(const string& s) { int l=0, r=s.size()-1; while(l<r) { if(s[l++]!=s[r--]) return false; } return true; } Avoid creating a reversed copy and comparing — that's O(n) space unnecessarily.

Q: How do you trim leading and trailing whitespace from a string?

A: Use find_first_not_of and find_last_not_of: s.erase(0, s.find_first_not_of(" \t\n\r")); s.erase(s.find_last_not_of(" \t\n\r")+1); If the string is all whitespace, find_first_not_of returns npos — handle this edge case by checking first.

Common Pitfalls

  • Comparing find() result with int -1: find() returns size_t. Comparing with == -1 compares a large unsigned value with a negative signed one — always use string::npos.
  • O(n²) string concatenation in loops: Using result = result + s in a loop creates a new string each iteration. Use result += s or an ostringstream.
  • substr with invalid positions: substr(pos, len) throws out_of_range if pos > size(). Validate positions before calling.

Best Practices

  • Always compare find() results against std::string::npos, not -1.
  • Use string::reserve() when building strings iteratively — avoids repeated reallocations.
  • Use std::from_chars / to_chars for performance-critical number conversions — they are locale-independent and allocation-free.