Longest Common Prefix

Approach 1: Pairwise Comparison - Time Complexity O(m*n)

class CommonPrefixFinder {
public:
    string findLongestCommonPrefix(vector& words) 
    {
       // Pairwise comparison
       string result = words[0];
       size_t count = words.size();
       for(size_t i = 0; i < count; ++i)
          result = findCommon(result, words[i]);
            return result;
    }
    
    string findCommon(string& first, string& second)
    {
        size_t minLength = min(first.size(), second.size());
        size_t i = 0;
        for(; i < minLength; ++i)
           if(first[i] != second[i]) break;
        return first.substr(0, i);
    }
};

Approach 2: Unified Comparison - Time Complexity O(m*n)

class CommonPrefixFinder {
public:
    string findLongestCommonPrefix(vector& words) 
    {
        // Unified comparison
        size_t wordCount = words.size(), charCount = words[0].size();
        for(int i = 0; i < charCount; ++i)
        {
            char currentChar = words[0][i];
            for(int j = 0; j < wordCount; ++j)
             if(i == words[j].size() || words[j][i] != currentChar)
              return words[0].substr(0, i); 
        }
        return words[0]; // Edge case: single string
    }
};

Longest Palindromic Substring

Solution: Center Expansion Algorithm

1. Fix a center point and expand outward in both directions

2. Consider both odd and even length palindromes

class PalindromeFinder {
public:
    string findLongestPalindrome(string input) 
    {
        size_t start = 0; size_t maxLength = 0;
        // Center expansion algorithm
        size_t n = input.size();
        for(size_t i = 0; i < n; ++i)
        {
            int left = i, right = i; // Odd length palindrome
            while(left >= 0 && right < n && input[left] == input[right]) 
            {
                --left;
                ++right;
            }
            if(right - left - 1 > maxLength) 
            {
                start = left + 1;
                maxLength = right - left - 1;
            }
            // Even length palindrome
             left = i; right = i + 1;
            while(left >= 0 && right < n && input[left] == input[right]) 
            {
                --left;
                ++right;
            }
            if(right - left - 1 > maxLength) 
            {
                start = left + 1;
                maxLength = right - left - 1;
            }
        }
        return input.substr(start, maxLength);
    }
};

Binary String Addition

Solution: Simulate carry addition with base-2 arithmetic, then reverse the result.

class BinaryAdder {
public:
    string addBinaryStrings(string a, string b) {
    // Simulate carry addition with base-2
    size_t len1 = a.size(), len2 = b.size();
    string result;
    result.reserve(len1 > len2 ? len1 + 1 : len2 + 1);
    int pos1 = len1 - 1; 
    int pos2 = len2 - 1;
    int carry = 0;
    while(pos1 >= 0 || pos2 >= 0 || carry) 
    {
       if(pos1 >= 0) carry += a[pos1--] - '0';
       if(pos2 >= 0) carry += b[pos2--] - '0';
        result += (carry % 2) + '0';
        carry /= 2;
    }
    reverse(result.begin(), result.end());
    return result;
    }
};

Length of Last Word

This problem requires handling spaces properly. Using getline() and rfind() helps solve it efficiently.

#include 
using namespace std;

int main() 
{
   string input;
   getline(cin, input);
   cout << input.size() - 1 - input.rfind(" ") << endl;
   return 0;
}

Alternatively, we could use cin >> input repeatedly, which would capture only the last word.

Reverse Only Letters

Non-letter characters remain in place while letters are reversed. We can use a two-pointer approach.

class LetterReverser {
public:
    string reverseLettersOnly(string input)
    {
        // Two-pointer approach
          size_t left = 0;
          size_t right = input.size() - 1;
          while(left < right)
          {
              while(left < right && !isalpha(input[left])) ++left;
              while(left < right && !isalpha(input[right]))   --right;
              swap(input[left], input[right]);
              ++left;
              --right;
          }
          return input;
    }
};

Valid Palindrome

Use two pointers moving towards the center, skipping non-alphanumeric characters.

class PalindromeValidator {
public:
    bool isValidPalindrome(string input)
    {
      // Two pointers moving toward center
       int length = input.size();
       int left = 0, right = length - 1;
       while(left < right)
       {
         while(left < right && !isalnum(input[left]))  ++left;
         while(left < right && !isalnum(input[right])) --right;
         if(left < right)
             if(tolower(input[left]) != tolower(input[right]))
                  return false;
         ++left;
         --right;
       }
       return true;
    }
};

Reverse String II

Reverse every k characters in a string, leaving the remainder as is.

class StringReverserII {
public:
    string reverseInChunks(string input, int k)
    {
        int n = input.size();
        for(int i = 0; i < n; i += 2 * k)
             reverse(input.begin() + i, input.begin() + min(i + k, n));
        return input;
    }
};

Note: If i+k exceeds the string length, we adjust it to n.

Reverse Words in a String III

Use two pointers to identify word boundaries and reverse each word individually.

class WordReverser {
public:
    string reverseEachWord(string input)
    {
          int start = 0, end = 0;
          int length = input.size();
          while(start < length)
          {
             if(input[start] != ' ')
             {
                 while(end < length && input[end] != ' ')
                 ++end;
                 reverse(input.begin() + start, input.begin() + end);
             }
             ++end;
             start = end;
          }
          return input;
    }
};

String Multiplication

Multiply two numbers represented as strings efficiently.

class StringMultiplier {
public:
       string multiplyNumbers(string num1, string num2)
    { 
      if(num1 == "0" || num2 == "0") return "0";
      string result = "0";
      int m = num1.size(), n = num2.size();
      for(int i = n-1; i >= 0; --i)
      {
        string current;
        int carry = 0;
        for(int j = n-1; j > i; --j) 
           current.push_back('0');
        int y = num2[i] - '0';
        for(int j = m-1; j >= 0; --j)
        {
            int x = num1[j] - '0';
            int product = x * y + carry;
            current.push_back(product % 10 + '0');
            carry = product / 10;
        }
        while(carry != 0)
         {
            current.push_back(carry % 10 + '0');
            carry /= 10;
         }
         reverse(current.begin(), current.end());
         result = addBinaryStrings(result, current);
      }
       return result;
    }

string addBinaryStrings(string a, string b) {
    size_t len1 = a.size(), len2 = b.size();
    string result;
    result.reserve(len1 > len2 ? len1 + 1 : len2 + 1);
    int pos1 = len1 - 1; 
    int pos2 = len2 - 1;
    int carry = 0;
    while(pos1 >= 0 || pos2 >= 0 || carry) 
    {
       if(pos1 >= 0) carry += a[pos1--] - '0';
       if(pos2 >= 0) carry += b[pos2--] - '0';
        result += (carry % 10) + '0';
        carry /= 10;
    }
    reverse(result.begin(), result.end());
    return result;
    }
};

Alternative approach:

class StringMultiplier {
public:
    string multiply(string num1, string num2) 
    {
      // Handle multiplication: 1. Multiply without carry 2. Sum results 3. Process carry 4. Remove leading zeros
      size_t m = num1.size(), n = num2.size();
      // Reverse strings to simplify processing
      reverse(num1.begin(), num1.end());
      reverse(num2.begin(), num2.end());
      vector temp(m + n - 1);
      for(size_t i = 0; i < m; ++i) // Multiply without carry
        for(size_t j = 0; j < n; ++j) 
          temp[i+j] += (num1[i] - '0') * (num2[j] - '0');
      // Process carry
      size_t pos = 0, carry = 0;
      string result;
      result.reserve(m + n);
      while(pos < m + n - 1 || carry) 
      {
        if(pos < m + n - 1) carry += temp[pos++];
           result += (carry % 10) + '0';
             carry /= 10;
      }
      // Remove leading zeros
      while(result.size() > 1 && result.back() == '0') result.pop_back();
      reverse(result.begin(), result.end());
      return result;
    }
};

Common String Operations

C language string functions:

Reference: Character and String Functions in C

C++ string class operations:

Reference: Using the C++ String Class