String Rotation and Reversal Techniques

Problem: Move first m characters to the end

Brute Force Rotation

Move one character to the end, repeat m times. Time complexity O(mn), space O(1).

Three-Step Reversal

Time complexity O(N), space O(1). Split into two parts, reverse each part, then reverse the whole string.

void reverse(string &s, int from, int to) {
    while(from < to) swap(s[from++], s[to--]);
}

void ReverseStr(string &s, int m) {
    int n = s.length();
    // m might be greater than n
    m %= s.length();

    reverse(s, 0, m-1);
    reverse(s, m, n-1);
    reverse(s, 0, n-1);
}

151. Reverse Words in a String

The idea works like character reversal but for words. First reverse the entire string, which reverses each word’s order. Then scan for spaces with two pointers and reverse individual words. Finally reverse the last word.

Catch: Remove leading, middle, and trailing spaces. Time complexity: O(N) Space complexity: O(1)

void reverseWords(string &s) {
    //trimming spaces at start
    int i=0;
    while(i<s.length() && s[i]==' '){
        s.erase(s.begin()+i);
    }

    //trimming spaces from the end.
    int j=s.length()-1;
    while(j>=0 && s[j]==' '){
        s.erase(s.begin()+j);
        j--;
    }

	// CC: string contains only spaces
    if (s == "") return;
	// 1. reverse whole str
    reverse(s, 0, s.length()-1);
    
	// 2. reverse word by word (two pointers)
    for(i=j=0;i<s.length()-1;++i) {
        if (s[i] == ' ') {
            reverse(s, j, i-1);
            j = i+1;
			// CC: remove spaces before continue
            while (s[i+1] == ' ') s.erase(s.begin()+i+1);
        }
    }
    reverse(s, j, s.length()-1);
}

void reverse(string &s, int from, int to) {
    while(from < to) swap(s[from++], s[to--]);
}

Key Insight

Efficient string reversal uses three reversals.

796. Rotate String

Given strings a and b. Check if b can be obtained by left-shifting a.

Solution 1: Brute Force Substring Concatenation 0ms

b can be obtained by splitting a at some position and swapping parts.

bool rotateString(string a, string b) {
    if (a.length() != b.length()) return false;
    if (a == b) return true;

    for(int i=0;i<a.size();++i) {
		// reduce unnecessary splits
        if (a[i] != b[0]) continue;
        if (a.substr(i, a.size()-i)
			+a.substr(0, i) == b) return true;
    }

    return false;
}

Solution 2: Pattern Recognition 4ms

b will always appear in the new string made by concatenating two copies of a.

bool rotateString(string A, string B) {
    return A.size() == B.size() && (A + A).find(B) != string::npos;
}

Key Insight

string::npos is just -1 indicating not found.

#two-pointers #strings

String Permutation Detection: Two Sliding Window Approaches String to Integer Conversion