Navigation

DSA interview 11 min read

Top String Interview Questions with Solutions (C++, Java, JS, Python)

This page gathers the string interview questions that interviewers reach for most: anagrams, palindromes, sliding-window substring problems, and stack-based parsing. Each entry gives the problem, the approach, the complexity, and a full solution in C++, Java, JavaScript, and Python via the language switcher. New to strings as a data structure? Start with the strings introduction.

Pattern preview: Most string questions reduce to four ideas — frequency counting with a hash map, two pointers from both ends, a sliding window for substrings, and a stack for matching. Spot the pattern and the code writes itself.

1. Valid Anagram

Question. Given two strings s and t, return true if t is an anagram of s (same characters, same counts).

Approach. If the lengths differ they cannot match. Otherwise count characters in s, then decrement while scanning t; any count going negative means a mismatch.

Complexity. O(n) time, O(1) space for a fixed alphabet (O(k) for k distinct characters).

#include <string>
#include <unordered_map>

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

import java.util.HashMap;
import java.util.Map;

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

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

from collections import Counter

def is_anagram(s, t):
    return Counter(s) == Counter(t)

2. Valid Palindrome

Question. Return true if a string is a palindrome considering only alphanumeric characters and ignoring case.

Approach. Two pointers from both ends. Skip non-alphanumeric characters, then compare lowercased characters; move inward.

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

#include <string>
#include <cctype>

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

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

function isPalindrome(s) {
  const isAlnum = c => /[a-z0-9]/i.test(c);
  let i = 0, j = s.length - 1;
  while (i < j) {
    while (i < j && !isAlnum(s[i])) i++;
    while (i < j && !isAlnum(s[j])) j--;
    if (s[i].toLowerCase() !== s[j].toLowerCase()) return false;
    i++; j--;
  }
  return true;
}

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

3. Longest Substring Without Repeating Characters

Question. Find the length of the longest substring with all distinct characters.

Approach. A sliding window. Track the last index where each character appeared; when you hit a repeat that lies inside the window, jump the window’s start just past it. The window [start, i] is always duplicate-free.

Complexity. O(n) time, O(k) space (k distinct characters).

#include <string>
#include <unordered_map>
#include <algorithm>

int lengthOfLongestSubstring(const std::string& s) {
    std::unordered_map<char, int> last;
    int best = 0, start = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        auto it = last.find(s[i]);
        if (it != last.end() && it->second >= start) start = it->second + 1;
        last[s[i]] = i;
        best = std::max(best, i - start + 1);
    }
    return best;
}

import java.util.HashMap;
import java.util.Map;

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

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

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

4. Group Anagrams

Question. Group a list of strings so that anagrams of each other land in the same group.

Approach. Two anagrams share a sorted-character signature. Use that sorted string as a hash-map key and bucket each word under it.

Complexity. O(n · k log k) time for n words of length up to k, O(n · k) space.

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
    std::unordered_map<std::string, std::vector<std::string>> groups;
    for (const std::string& s : strs) {
        std::string key = s;
        std::sort(key.begin(), key.end());
        groups[key].push_back(s);
    }
    std::vector<std::vector<std::string>> res;
    for (auto& kv : groups) res.push_back(kv.second);
    return res;
}

import java.util.*;

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        char[] c = s.toCharArray();
        Arrays.sort(c);
        groups.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

function groupAnagrams(strs) {
  const groups = new Map();
  for (const s of strs) {
    const key = [...s].sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(s);
  }
  return [...groups.values()];
}

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        groups["".join(sorted(s))].append(s)
    return list(groups.values())

5. Valid Parentheses

Question. Given a string of ()[]{}, decide if every bracket is closed by the correct type in the correct order.

Approach. Use a stack. Push opening brackets; on a closing bracket, the top must be its matching opener. The string is valid only if the stack ends empty.

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

#include <string>
#include <stack>
#include <unordered_map>

bool isValid(const std::string& s) {
    std::stack<char> st;
    std::unordered_map<char, char> match = {{')', '('}, {']', '['}, {'}', '{'}};
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty() || st.top() != match[c]) return false;
            st.pop();
        }
    }
    return st.empty();
}

import java.util.ArrayDeque;
import java.util.Deque;

boolean isValid(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') st.push(')');
        else if (c == '[') st.push(']');
        else if (c == '{') st.push('}');
        else if (st.isEmpty() || st.pop() != c) return false;
    }
    return st.isEmpty();
}

function isValid(s) {
  const st = [];
  const match = { ")": "(", "]": "[", "}": "{" };
  for (const c of s) {
    if (c === "(" || c === "[" || c === "{") st.push(c);
    else if (st.pop() !== match[c]) return false;
  }
  return st.length === 0;
}

def is_valid(s):
    st = []
    match = {")": "(", "]": "[", "}": "{"}
    for c in s:
        if c in "([{":
            st.append(c)
        elif not st or st.pop() != match[c]:
            return False
    return not st

6. Reverse Words in a String

Question. Reverse the order of words in a sentence, collapsing extra spaces (" the sky " → "sky the").

Approach. Split on whitespace, drop empties, reverse the list, and re-join with single spaces.

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

#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

std::string reverseWords(const std::string& s) {
    std::istringstream iss(s);
    std::vector<std::string> words;
    std::string w;
    while (iss >> w) words.push_back(w);
    std::reverse(words.begin(), words.end());
    std::string res;
    for (size_t i = 0; i < words.size(); i++) {
        if (i) res += ' ';
        res += words[i];
    }
    return res;
}

String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        sb.append(words[i]);
        if (i > 0) sb.append(' ');
    }
    return sb.toString();
}

function reverseWords(s) {
  return s.trim().split(/\s+/).reverse().join(" ");
}

def reverse_words(s):
    return " ".join(s.split()[::-1])

7. Longest Common Prefix

Question. Find the longest common prefix shared by an array of strings (empty if none).

Approach. Start with the first string as the candidate prefix; for each remaining string, shrink the prefix to the matching leading characters. Stop early if it becomes empty.

Complexity. O(n · m) time for n strings of length up to m, O(1) extra space.

#include <vector>
#include <string>

std::string longestCommonPrefix(const std::vector<std::string>& strs) {
    if (strs.empty()) return "";
    std::string prefix = strs[0];
    for (size_t i = 1; i < strs.size(); i++) {
        size_t j = 0;
        while (j < prefix.size() && j < strs[i].size() && prefix[j] == strs[i][j]) j++;
        prefix = prefix.substr(0, j);
        if (prefix.empty()) break;
    }
    return prefix;
}

String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        int j = 0;
        while (j < prefix.length() && j < strs[i].length()
               && prefix.charAt(j) == strs[i].charAt(j)) j++;
        prefix = prefix.substring(0, j);
        if (prefix.isEmpty()) break;
    }
    return prefix;
}

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    let j = 0;
    while (j < prefix.length && j < strs[i].length && prefix[j] === strs[i][j]) j++;
    prefix = prefix.slice(0, j);
    if (prefix === "") break;
  }
  return prefix;
}

def longest_common_prefix(strs):
    if not strs:
        return ""
    prefix = strs[0]
    for s in strs[1:]:
        j = 0
        while j < len(prefix) and j < len(s) and prefix[j] == s[j]:
            j += 1
        prefix = prefix[:j]
        if not prefix:
            break
    return prefix

Pitfall: With Unicode, “characters” are not bytes — a fixed 26-slot count or a naive index can break on accented or emoji input. Clarify the alphabet during the interview and prefer a hash map when in doubt.

Keep practicing

You now have the core string toolkit: frequency counts, two pointers, sliding windows, sorted-signature hashing, and stacks. Practice more on the string exercises, then tackle tree & graph interview questions.