Strings in C++: Interview Problem Solving & String Sorting

An in-depth guide to solving core string algorithmic interview problems in C++. This chapter covers four foundational string problems: defanging IP addresses, verifying 2-place string rotations, checking for pangrams, and optimizing string sorting from $O(N^2)$ down to linear $O(N)$ time using frequency arrays.

1. Problem 1: Defanging an IP Address – Problem Statement & Mental Model

Problem Premise

A defanged IP address replaces every period "." in a standard IPv4 address string with the bracketed sequence "[.]". Defanging is commonly used in cybersecurity to prevent automated scripts from inadvertently parsing IP addresses as actionable hyperlinks.

Examples

• Example 1:
  • Input: address = "1.1.1.1"
  • Output: "1[.]1[.]1[.]1"
• Example 2:
  • Input: address = "255.100.50.0"
  • Output: "255[.]100[.]50[.]0"

Note: IPv4 addresses consist of four 8-bit octets separated by dots, totaling 32 bits of binary data formatted into decimal notation.

Core Mental Model

A string in C++ behaves fundamentally like a 1D character array indexed from 0 to size - 1. To construct the defanged address, iterate sequentially through every character index.

Naive vs. Modular Approach

1. In-place replacement (Naive/Complex): Replacing a 1-character '.' with a 3-character "[.]" in-place requires shifting all trailing elements to the right repeatedly, leading to an $O(N^2)$ time complexity.
2. Linear String Construction (Optimal): Instantiate an empty output string answer. Traversal inspects each character:
   • If address[index] == '.', append string "[.]".
   • Otherwise, append character address[index].

2. Defanging an IP Address – Step-by-Step Algorithm & C++ Implementation

Vertical Execution Flow

Production C++ Implementation

#include <iostream>
#include <string>

class Solution {
public:
    std::string defangIPaddr(std::string address) {
        std::string answer = "";
        int index = 0;
        
        while (index < address.size()) {
            if (address[index] == '.') {
                answer += "[.]";
            } else {
                answer += address[index];
            }
            index++;
        }
        
        return answer;
    }
};

Complexity & Edge Case Analysis

• Time Complexity: $\mathcal{O}(N)$, where $N$ is the length of the string address. We inspect each character exactly once.
• Space Complexity: $\mathcal{O}(N)$ auxiliary space required to store the newly constructed result string.
• Common Pitfall: Forgetting to increment index inside the while loop leads to an infinite loop. Always double-check loop termination variables during dry runs.

3. Problem 2: String Rotation by Two Places – Conceptual Framework

Problem Premise

Given two strings string1 and string2, determine if string1 can be rotated by exactly 2 positions (either clockwise or anti-clockwise) such that it becomes equal to string2.

Input:  string1 = "amazon", string2 = "azonam"
Output: 1 (True - Anti-clockwise rotation by 2 places yields "azonam")

Input:  string1 = "amazon", string2 = "onamaz"
Output: 1 (True - Clockwise rotation by 2 places yields "onamaz")

Directional Rotations Explained

1. Clockwise Rotation (Shift Right / Cyclic Shift)

In a clockwise rotation, characters shift towards higher indices. The character at the final index wraps around to index 0.

Original:  a  m  a  z  o  n
Shift 1:   n  a  m  a  z  o
Shift 2:   o  n  a  m  a  z

2. Anti-Clockwise Rotation (Shift Left / Cyclic Shift)

In an anti-clockwise rotation, characters shift towards lower indices. The character at index 0 wraps around to the final index.

Original:  a  m  a  z  o  n
Shift 1:   m  a  z  o  n  a
Shift 2:   a  z  o  n  a  m

4. String Rotation by Two Places – C++ Implementation & Reference Mechanics

Memory Model: Pass-by-Value vs. Pass-by-Reference

When passing strings into auxiliary helper functions, standard pass-by-value creates a local copy. Modifications made to the string inside the function are lost upon returning.

To modify the rotation state persistently across function calls, pass the string as a reference (std::string &s).

In-Place Single-Step Rotation Algorithms

Clockwise Single Shift Mechanism

1. Store the final character: char lastChar = s[s.size() - 1].
2. Shift elements rightward starting from index s.size() - 2 down to 0: s[i + 1] = s[i].
3. Assign stored character to start: s[0] = lastChar.

Anti-Clockwise Single Shift Mechanism

1. Store the first character: char firstChar = s[0].
2. Shift elements leftward starting from index 1 up to s.size() - 1: s[i - 1] = s[i].
3. Assign stored character to end: s[s.size() - 1] = firstChar.

Complete Production C++ Code

#include <iostream>
#include <string>

class Solution {
private:
    // Rotates string clockwise by 1 position in-place
    void rotateClockwise(std::string &s) {
        char lastChar = s[s.size() - 1];
        for (int i = s.size() - 2; i >= 0; i--) {
            s[i + 1] = s[i];
        }
        s[0] = lastChar;
    }

    // Rotates string anti-clockwise by 1 position in-place
    void rotateAntiClockwise(std::string &s) {
        char firstChar = s[0];
        for (int i = 1; i < s.size(); i++) {
            s[i - 1] = s[i];
        }
        s[s.size() - 1] = firstChar;
    }

public:
    bool isRotated(std::string str1, std::string str2) {
        if (str1.size() != str2.size()) {
            return false;
        }
        if (str1.size() < 2) {
            return str1 == str2;
        }

        // Test Clockwise Rotation by 2 places
        std::string clockwiseStr = str1;
        rotateClockwise(clockwiseStr);
        rotateClockwise(clockwiseStr);
        if (clockwiseStr == str2) {
            return true;
        }

        // Test Anti-Clockwise Rotation by 2 places
        std::string antiClockwiseStr = str1;
        rotateAntiClockwise(antiClockwiseStr);
        rotateAntiClockwise(antiClockwiseStr);
        if (antiClockwiseStr == str2) {
            return true;
        }

        return false;
    }
};

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$, where $N$ is the length of str1. Each rotation pass shifts $N$ elements. Performing 4 total passes takes $4 \times \mathcal{O}(N) = \mathcal{O}(N)$ time.
• Space Complexity: $\mathcal{O}(N)$ to store copy strings clockwiseStr and antiClockwiseStr.

5. Problem 3: Check if Sentence is Pangram – Concept & Frequency Mapping

Problem Premise

A Pangram is a sentence containing every letter of the English alphabet at least once (focusing on lowercase letters 'a' through 'z').

Input:  sentence = "thequickbrownfoxjumpsoverthelazydog"
Output: true (All 26 characters 'a'-'z' are present)

Input:  sentence = "leetcode"
Output: false (Missing multiple characters such as 'a', 'b', 'f', etc.)

Index Mapping via ASCII Mathematics

Rather than searching the entire string 26 times ($26 \times N$ operations), we maintain a boolean frequency array of fixed size 26.

Character: 'a'  'b'  'c'  'd'  ...  'z'
ASCII:      97   98   99  100  ...  122
Index:       0    1    2    3  ...   25

Formula: index = character - 'a'
Examples:
  'a' - 'a' = 97 - 97 = 0
  'b' - 'a' = 98 - 97 = 1
  'z' - 'a' = 122 - 97 = 25

Algorithm Flow

1. Allocate a boolean array/vector alpha of size 26, initialized to 0 (false).
2. Iterate through each character ch in sentence.
3. Set alpha[ch - 'a'] = true.
4. After traversal, iterate through alpha. If any index contains false (0), return false.
5. If all 26 indices are true, return true.

6. Check if Sentence is Pangram – C++ Code & Complexity Analysis

C++ Source Code

#include <iostream>
#include <string>
#include <vector>

class Solution {
public:
    bool checkIfPangram(std::string sentence) {
        // Frequency/Presence vector for 26 lowercase English letters
        std::vector<bool> alpha(26, false);

        // Mark character presence
        for (int i = 0; i < sentence.size(); i++) {
            int index = sentence[i] - 'a';
            alpha[index] = true;
        }

        // Verify all 26 letters are present
        for (int i = 0; i < 26; i++) {
            if (!alpha[i]) {
                return false; // Found missing character
            }
        }

        return true;
    }
};

Complexity Analysis

• Time Complexity: $\mathcal{O}(N + 26) = \mathcal{O}(N)$, where $N$ is the string length. Traversing the sentence takes $\mathcal{O}(N)$, and scanning the 26-element array takes constant time $\mathcal{O}(1)$.
• Space Complexity: $\mathcal{O}(26) = \mathcal{O}(1)$ auxiliary space. The boolean vector size is fixed at 26 regardless of sentence length.

7. Problem 4: Sorting a String – Naive vs. Optimal Counting Sort

Problem Premise

Given a string s containing lowercase English letters, reorder its characters in non-decreasing alphabetical order.

Input:  s = "eabcabd"
Output: "aabbcde"

Comparing Sorting Frameworks

The $\mathcal{O}(N)$ Counting Principle

Since the domain of characters is bounded to lowercase English letters ('a' to 'z'), we don't need comparison-based sorting.

1. Count Step: Count frequency of each character into a size-26 integer array.
2. Reconstruction Step: Rebuild the output string alphabetically using character frequencies.

8. Sorting a String – C++ Implementation & Reconstruction Mechanics

Character Type Casting Mechanics

To convert an integer array index $i$ back into its character representation:

• For $i = 0$: $'a' + 0 = 97 \xrightarrow{\text{cast}} 'a'$
• For $i = 1$: $'a' + 1 = 98 \xrightarrow{\text{cast}} 'b'$

C++ Source Code

#include <iostream>
#include <string>
#include <vector>

class Solution {
public:
    std::string sortString(std::string s) {
        // Step 1: Create frequency vector initialized to 0
        std::vector<int> alpha(26, 0);

        // Step 2: Populate frequencies
        for (int i = 0; i < s.size(); i++) {
            alpha[s[i] - 'a']++;
        }

        // Step 3: Reconstruct sorted string
        std::string answer = "";
        for (int i = 0; i < 26; i++) {
            char c = 'a' + i; // Map index back to character
            while (alpha[i] > 0) {
                answer += c;
                alpha[i]--; // Decrement frequency
            }
        }

        return answer;
    }
};

Complexity Analysis

• Time Complexity: $\mathcal{O}(N + 26) = \mathcal{O}(N)$.
  • Frequency accumulation takes $\mathcal{O}(N)$.
  • String reconstruction appends $N$ total characters across 26 outer iterations, yielding $\mathcal{O}(26 + N) = \mathcal{O}(N)$.
• Space Complexity: $\mathcal{O}(26) = \mathcal{O}(1)$ auxiliary space (excluding the output string space).

9. Comprehensive Summary Table & Complexity Comparison

10. Summary and Key Takeaways

1. String as 1D Character Arrays: Strings in C++ store contiguous character data. Operations on strings mirror 1D array manipulations with zero-indexed offsets.
2. ASCII Arithmetic for Index Hashing: The expression ch - 'a' maps lowercase letters 'a'–'z' to array indices 0–25 in $\mathcal{O}(1)$ time, eliminating the need for dynamic hash maps.
3. Avoid In-Place Expansion: Replacing single characters with multi-character strings in-place causes repetitive shifting ($\mathcal{O}(N^2)$ time). Accumulating characters into a new result string achieves linear $\mathcal{O}(N)$ performance.
4. Pass-by-Reference Nuance: Functions that perform structural modifications (such as cyclic rotations) must pass string parameters by reference (std::string &s) to avoid redundant copying and retain changes in caller scope.
5. Counting Sort Bypasses Comparison Limits: While comparison-based sorting algorithms (std::sort) operate in $\mathcal{O}(N \log N)$ time, bounded alphabet strings can be sorted in optimal linear $\mathcal{O}(N)$ time using frequency counting.
6. Fixed Frequency Arrays Yield $\mathcal{O}(1)$ Auxiliary Space: A 26-element array allocates fixed memory regardless of whether the input string contains 10 or 1,000,000 characters, guaranteeing strict $\mathcal{O}(1)$ auxiliary space complexity.