This article covers two classic string manipulation problems that demonstrate the power of in-place operations and the three-step reverse technique. We'll also introduce the KMP algorithm for pattern matching.

151. Reverse Words in a String

String manipulation in C++ offers a significant advantage over some other languages: we can modify strings in-place, achieving O(1) space complexity. This problem requires removing extra spaces and reversing the order of words.

The algorithm follows these three steps:

1. Remove all extra spaces from the string
2. Reverse the entire string
3. Reverse each individual word within the string

class Solution {
public:
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    
    void removeExtraSpaces(string& s) {
        int writeIndex = 0;
        for (int readIndex = 0; readIndex < s.size(); readIndex++) {
            if (s[readIndex] != ' ') {
                if (writeIndex != 0) {
                    s[writeIndex] = ' ';
                    writeIndex++;
                }
                while (readIndex < s.size() && s[readIndex] != ' ') {
                    s[writeIndex] = s[readIndex];
                    writeIndex++;
                    readIndex++;
                }
            }
        }
        s.resize(writeIndex);
    }

    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s, 0, s.size() - 1);
        
        int wordStart = 0;
        for (int i = 0; i <= s.size(); i++) {
            if (i == s.size() || s[i] == ' ') {
                reverse(s, wordStart, i - 1);
                wordStart = i + 1;
            }
        }
        return s;
    }
};

Time Complexity: O(n)
Space Complexity: O(1)

Kama Code 55. Right Rotation String

This problem demonstrates an elegant three-reverse technique for rotating strings. Given an integer k, rotate the string to the right by k positions.

The key insight is that a right rotation by k positions equals reversing the last k characters and prepending them to the front. This can be achieved with three simple reversals:

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int rotation;
    string str;
    cin >> rotation;
    cin >> str;
    
    int k = rotation % str.length();
    
    reverse(str.begin(), str.end());
    reverse(str.begin(), str.begin() + k);
    reverse(str.begin() + k, str.end());
    
    cout << str << endl;
    
    return 0;
}

For example, with "abcXYZdef" and k=3:
Step 1: Reverse entire string → "fedZYXcba"
Step 2: Reverse first k characters → "edfZYXcba"
Step 3: Reverse remaining characters → "XYZdefabc"

Python Alternative (uses O(n) extra space):

k = int(input())
string = input()

length = len(string)
shift = k % length

first_part = string[:length - shift]
second_part = string[length - shift:]

result = second_part + first_part
print(result)

Introduction to KMP Algorithm

The Knuth-Morris-Pratt (KMP) algorithm efficiently finds pattern occurrences in a string with a time complexity of O(n + m). It preprocesses the pattern to build a "failure function" or "prefix table" that helps skip characters during matching.

Key concepts:

• Prefix Table (LPS Array): For each position i, stores the length of the longest proper prefix that is also a suffix in the substring pattern[0...i]
• Key Observation: When a mismatch occurs, we don't need to restart matching from the beginning—we can use the prefix table to determine the next starting position

The KMP algorithm is particularly useful for problems like:

• Finding the first occurrence of a pattern (LeetCode 28)
• Detecting repeated substring patterns (LeetCode 459)

The repeated substring pattern problem leverages a clever observation: if a string is composed of repeating patterns, concatenating the string with itself and removing the first and last characters should still contain the original string.

Summary

These problems highlight important string manipulation techniques: in-place reversal for O(1) space complexity, the three-step reverse method for rotations, and pattern matching algorithms like KMP for efficient searching.