Navigation

DSA arrays 11 min read

String Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the string exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and common pitfalls. Try the problems first — then check your work here.

Q1. Reverse a string

Idea: Build a character buffer you can mutate (or use two pointers on one), swap ends inward, then join. C++ strings are mutable; Java/JS/Python need a copy because their strings are immutable.

Complexity: O(n) time, O(n) space (output string).

#include <string>
#include <algorithm>
std::string reverseString(std::string s) {
    std::reverse(s.begin(), s.end()); // in place, s is mutable
    return s;
}

String reverseString(String s) {
    return new StringBuilder(s).reverse().toString();
}

function reverseString(s) {
  return s.split("").reverse().join("");
}

def reverse_string(s):
    return s[::-1]

Pitfall: Trying s[i] = ... on a Java, JavaScript, or Python string fails or silently does nothing — they are immutable. Convert to an array/builder first.

Q2. Check a palindrome

Idea: Two pointers from both ends moving inward; if any pair differs, it’s not a palindrome. No extra copy needed.

Complexity: O(n) time, O(1) extra space.

#include <string>
bool isPalindrome(const std::string& s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++; j--;
    }
    return true;
}

boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) return false;
        i++; j--;
    }
    return true;
}

function isPalindrome(s) {
  let i = 0, j = s.length - 1;
  while (i < j) {
    if (s[i] !== s[j]) return false;
    i++; j--;
  }
  return true;
}

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

Pitfall: If the problem says “ignore case and non-alphanumeric characters,” normalize first (lowercase + filter) or skip non-alphanumerics with the two pointers. The bare version above compares raw characters.

Q3. Count vowels

Idea: Single pass; check membership in a small vowel set (lowercase the character to handle both cases).

Complexity: O(n) time, O(1) space.

#include <string>
#include <cctype>
int countVowels(const std::string& s) {
    int count = 0;
    for (char c : s) {
        char l = std::tolower((unsigned char)c);
        if (l == 'a' || l == 'e' || l == 'i' || l == 'o' || l == 'u') count++;
    }
    return count;
}

int countVowels(String s) {
    int count = 0;
    for (char c : s.toLowerCase().toCharArray())
        if ("aeiou".indexOf(c) >= 0) count++;
    return count;
}

function countVowels(s) {
  let count = 0;
  for (const c of s.toLowerCase())
    if ("aeiou".includes(c)) count++;
  return count;
}

def count_vowels(s):
    vowels = set("aeiou")
    return sum(1 for c in s.lower() if c in vowels)

Pitfall: Forgetting case — counting only lowercase misses A, E, etc. Normalize case before checking.

Q4. Valid anagram

Idea: Two strings are anagrams iff they have the same character counts. Tally one string up and the other down in a single frequency table; all zeros means a match. Different lengths can’t match.

Complexity: O(n) time, O(k) space (k = alphabet size).

#include <string>
#include <unordered_map>
bool isAnagram(const std::string& a, const std::string& b) {
    if (a.size() != b.size()) return false;
    std::unordered_map<char, int> freq;
    for (char c : a) freq[c]++;
    for (char c : b) {
        if (--freq[c] < 0) return false;
    }
    return true;
}

import java.util.HashMap;
import java.util.Map;
boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : a.toCharArray()) freq.merge(c, 1, Integer::sum);
    for (char c : b.toCharArray()) {
        int v = freq.getOrDefault(c, 0) - 1;
        if (v < 0) return false;
        freq.put(c, v);
    }
    return true;
}

function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const freq = new Map();
  for (const c of a) freq.set(c, (freq.get(c) || 0) + 1);
  for (const c of b) {
    const v = (freq.get(c) || 0) - 1;
    if (v < 0) return false;
    freq.set(c, v);
  }
  return true;
}

from collections import Counter
def is_anagram(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)

Pitfall: Sorting both strings and comparing also works but is O(n log n). The frequency-count approach is O(n). Also remember the length short-circuit.

Q5. First unique character

Idea: Two passes. First count every character’s frequency; then scan left to right and return the index of the first character with count 1.

Complexity: O(n) time, O(k) space.

#include <string>
#include <unordered_map>
int firstUniqChar(const std::string& s) {
    std::unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    for (int i = 0; i < (int)s.size(); i++)
        if (freq[s[i]] == 1) return i;
    return -1;
}

import java.util.HashMap;
import java.util.Map;
int firstUniqChar(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    for (int i = 0; i < s.length(); i++)
        if (freq.get(s.charAt(i)) == 1) return i;
    return -1;
}

function firstUniqChar(s) {
  const freq = new Map();
  for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);
  for (let i = 0; i < s.length; i++)
    if (freq.get(s[i]) === 1) return i;
  return -1;
}

from collections import Counter
def first_uniq_char(s):
    freq = Counter(s)
    for i, c in enumerate(s):
        if freq[c] == 1:
            return i
    return -1

Pitfall: Returning the first character whose count you haven’t seen again yet in one pass is wrong — you must finish counting before deciding uniqueness. Two passes (or count then scan) is the clean way.

Q6. Most frequent character

Idea: Build a frequency table, then take the character with the maximum count. Ties can be broken arbitrarily (here, the first one to reach the max).

Complexity: O(n) time, O(k) space.

#include <string>
#include <unordered_map>
char mostFrequent(const std::string& s) {
    std::unordered_map<char, int> freq;
    char best = s[0]; int bestCount = 0;
    for (char c : s) {
        int cnt = ++freq[c];
        if (cnt > bestCount) { bestCount = cnt; best = c; }
    }
    return best;
}

import java.util.HashMap;
import java.util.Map;
char mostFrequent(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    char best = s.charAt(0); int bestCount = 0;
    for (char c : s.toCharArray()) {
        int cnt = freq.merge(c, 1, Integer::sum);
        if (cnt > bestCount) { bestCount = cnt; best = c; }
    }
    return best;
}

function mostFrequent(s) {
  const freq = new Map();
  let best = s[0], bestCount = 0;
  for (const c of s) {
    const cnt = (freq.get(c) || 0) + 1;
    freq.set(c, cnt);
    if (cnt > bestCount) { bestCount = cnt; best = c; }
  }
  return best;
}

from collections import Counter
def most_frequent(s):
    return Counter(s).most_common(1)[0][0]

Pitfall: Calling this on an empty string indexes s[0] out of bounds. Validate non-empty input (or define a policy) before calling.

Q7. Longest substring without repeating characters

Idea: A sliding window with a “last seen index” map. Expand the right end one character at a time; when you hit a repeat that’s inside the window, jump the left end just past its previous position. Track the max window length. Each character is visited at most twice.

Complexity: O(n) time, O(k) space.

#include <string>
#include <unordered_map>
#include <algorithm>
int lengthOfLongest(const std::string& s) {
    std::unordered_map<char, int> last;
    int best = 0, left = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];
        if (last.count(c) && last[c] >= left) left = last[c] + 1;
        last[c] = right;
        best = std::max(best, right - left + 1);
    }
    return best;
}

import java.util.HashMap;
import java.util.Map;
int lengthOfLongest(String s) {
    Map<Character, Integer> last = new HashMap<>();
    int best = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (last.containsKey(c) && last.get(c) >= left) left = last.get(c) + 1;
        last.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

function lengthOfLongest(s) {
  const last = new Map();
  let best = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (last.has(c) && last.get(c) >= left) left = last.get(c) + 1;
    last.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

def length_of_longest(s):
    last = {}
    best = left = 0
    for right, c in enumerate(s):
        if c in last and last[c] >= left:
            left = last[c] + 1
        last[c] = right
        best = max(best, right - left + 1)
    return best

Pitfall: Only move left forward, never backward. The guard last[c] >= left ensures a repeat outside the current window doesn’t wrongly shrink it.

That’s the full answer sheet. Back to the string exercises or continue to linked lists.