Master string manipulation, palindrome detection, pattern matching, and advanced algorithms like KMP, sliding window, and dynamic programming on strings. From validation to pattern recognition, these problems cover essential string techniques.
Understanding string properties and manipulation techniques is critical for solving pattern matching and text processing problems efficiently. Strings are immutable in C#, so we use StringBuilder for mutations, frequency arrays for character analysis, and various scanning techniques for pattern detection.
Strings in C# are immutable. Every concatenation creates a new object, making repeated concatenation O(n²). Use StringBuilder for building strings in loops.
// Bad: O(n²) concatenation string result = ""; for (int i = 0; i < n; i++) { result += s[i]; // Creates new string each time } // Good: O(n) with StringBuilder var sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.Append(s[i]); } string result = sb.ToString();
Many string problems require counting character occurrences. Use a simple array for ASCII or small character sets (lowercase letters: 26 chars).
// Frequency array for lowercase English letters int[] freq = new int[26]; foreach (char c in s) { if (char.IsLower(c)) { freq[c - 'a']++; } } // Dictionary for arbitrary characters or Unicode var charCount = new Dictionary<char, int>(); foreach (char c in s) { if (!charCount.ContainsKey(c)) { charCount[c] = 0; } charCount[c]++; }
A palindrome reads the same forwards and backwards. Two main approaches: two-pointer scan or expand-around-center for longest palindromic substrings.
// Two-pointer approach bool IsPalindrome(string s) { int left = 0, right = s.Length - 1; while (left < right) { if (s[left] != s[right]) return false; left++; right--; } return true; } // Expand around center (for odd/even length palindromes) string ExpandAroundCenter(string s, int left, int right) { while (left >= 0 && right < s.Length && s[left] == s[right]) { left--; right++; } return s.Substring(left + 1, right - left - 1); }
Maintain a window of characters and slide it across the string. Useful for substring problems, minimum windows, and pattern matching.
// Template: Sliding window with frequency tracking int left = 0; var windowFreq = new Dictionary<char, int>(); for (int right = 0; right < s.Length; right++) { // Add right character to window if (!windowFreq.ContainsKey(s[right])) { windowFreq[s[right]] = 0; } windowFreq[s[right]]++; // Shrink window from left if needed while (WindowInvalid(windowFreq)) { windowFreq[s[left]]--; if (windowFreq[s[left]] == 0) { windowFreq.Remove(s[left]); } left++; } // Process valid window }
Many string problems use DP to avoid redundant substring checks. Build a 2D table where dp[i][j] typically represents the result for s[0..i] and t[0..j].
Given a string s, determine if it is a valid palindrome, considering only alphanumeric characters and ignoring cases. Return true if valid palindrome, false otherwise.
public bool IsPalindrome(string s) { int left = 0, right = s.Length - 1; while (left < right) { // Skip non-alphanumeric from left while (left < right && !char.IsLetterOrDigit(s[left])) { left++; } // Skip non-alphanumeric from right while (left < right && !char.IsLetterOrDigit(s[right])) { right--; } // Compare characters (case-insensitive) if (char.ToLower(s[left]) != char.ToLower(s[right])) { return false; } left++; right--; } return true; }
Input: "A man, a plan, a canal: Panama"
true| Aspect | Analysis |
|---|---|
| Time Complexity | O(n) — single pass with two pointers |
| Space Complexity | O(1) — only pointers, no extra storage |
| Empty/Single Char | Valid palindromes (true) |
| All Non-Alphanumeric | Valid palindrome (true) |
| Mixed Case | Handled by ToLower() conversion |
Given a string s, return the longest palindromic substring. If multiple exist with same length, return any one.
For each possible center (odd-length: single char; even-length: between chars), expand outward while characters match. Track the longest found.
public string LongestPalindrome(string s) { if (s.Length < 2) return s; int start = 0, maxLen = 1; // Helper: expand around center, return length int ExpandAroundCenter(int left, int right) { while (left >= 0 && right < s.Length && s[left] == s[right]) { left--; right++; } return right - left - 1; // Length of palindrome } // Check all centers: single char (odd) and between chars (even) for (int i = 0; i < s.Length; i++) { int len1 = ExpandAroundCenter(i, i); // Odd-length int len2 = ExpandAroundCenter(i, i + 1); // Even-length int len = Math.Max(len1, len2); if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; // Calculate start position } } return s.Substring(start, maxLen); }
Input: "babad"
"bab"| Aspect | Analysis |
|---|---|
| Time Complexity | O(n²) — n centers × O(n) expansion each |
| Space Complexity | O(1) — only tracking indices |
| Single Character | Return that character |
| No Palindrome > 1 | Return first character |
| Entire String Palindrome | Returns entire string correctly |
Given an array of characters s, reverse it in place without using extra space. The input is modified directly.
Use left and right pointers starting from opposite ends. Swap characters and move pointers toward center until they meet.
public void ReverseString(char[] s) { int left = 0, right = s.Length - 1; while (left < right) { // Swap char temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; } }
Input: ['h','e','l','l','o']
['o','l','l','e','h']| Aspect | Analysis |
|---|---|
| Time Complexity | O(n) — single pass, n/2 swaps |
| Space Complexity | O(1) — in-place, only temp variable |
| Single Character | No swap needed (left >= right immediately) |
| Even Length | All pairs swapped correctly |
| Odd Length | Middle character stays in place |
Convert a string to a 32-bit signed integer. Handle leading/trailing whitespace, optional sign, and clamp to [INT_MIN, INT_MAX]. Non-numeric characters stop parsing.
public int MyAtoi(string s) { int i = 0; int sign = 1; long result = 0; // Use long to detect overflow // Skip leading whitespace while (i < s.Length && s[i] == ' ') { i++; } if (i == s.Length) return 0; // All whitespace // Check sign if (s[i] == '+' || s[i] == '-') { sign = (s[i] == '-') ? -1 : 1; i++; } // Parse digits while (i < s.Length && char.IsDigit(s[i])) { int digit = s[i] - '0'; // Check overflow before multiplication if (result > int.MaxValue / 10 || (result == int.MaxValue / 10 && digit > 7)) { return sign == 1 ? int.MaxValue : int.MinValue; } result = result * 10 + digit; i++; } return (int)(result * sign); }
Input: " -42"
-42| Aspect | Analysis |
|---|---|
| Time Complexity | O(n) — single pass through string |
| Space Complexity | O(1) — constant space |
| Overflow (large positive) | Clamped to INT_MAX (2147483647) |
| Overflow (large negative) | Clamped to INT_MIN (-2147483648) |
| All whitespace / no digits | Returns 0 |
| Non-digit after number | Parsing stops, returns accumulated result |
long for intermediate result to safely detect overflow. Check result > INT_MAX / 10 before multiplying to avoid overflow in the check itself.The look-and-say sequence starts with "1". Each term describes the previous: count and say the digits. n=1 → "1", n=2 → "11" (one 1), n=3 → "21" (two 1s), n=4 → "1211", etc.
Start with "1" and iteratively generate the next term by counting consecutive identical characters.
public string CountAndSay(int n) { string current = "1"; // Generate n-1 iterations for (int i = 1; i < n; i++) { var sb = new StringBuilder(); int j = 0; while (j < current.Length) { char c = current[j]; int count = 1; // Count consecutive characters while (j + 1 < current.Length && current[j + 1] == c) { count++; j++; } // Append count and character sb.Append(count).Append(c); j++; } current = sb.ToString(); } return current; }
Generating n=4:
"1211"| Aspect | Analysis |
|---|---|
| Time Complexity | O(n * m) where m is length of current term (grows exponentially) |
| Space Complexity | O(m) for StringBuilder storing current term |
| n=1 | Returns "1" immediately |
| Large n | String grows exponentially; n ≤ 30 is practical limit |
| Consecutive chars | Counts correctly handled by inner while loop |
Given an array of strings, find the longest common prefix. If no common prefix, return empty string.
Compare characters column-by-column across all strings. Stop when a mismatch or end-of-string is found.
public string LongestCommonPrefix(string[] strs) { if (strs.Length == 0) return ""; // Find minimum length int minLen = strs[0].Length; for (int i = 1; i < strs.Length; i++) { minLen = Math.Min(minLen, strs[i].Length); } // Vertical scan: compare character by character for (int col = 0; col < minLen; col++) { char c = strs[0][col]; for (int row = 1; row < strs.Length; row++) { if (strs[row][col] != c) { // Mismatch found, return prefix up to this column return strs[0].Substring(0, col); } } } // All characters up to minLen match return strs[0].Substring(0, minLen); }
Input: ["flower","flow","flight"]
"fl"| Aspect | Analysis |
|---|---|
| Time Complexity | O(n * m) where n=num strings, m=min string length |
| Space Complexity | O(1) or O(m) for returned substring |
| Empty array | Returns empty string |
| Single string | Returns that string |
| No common prefix | Returns empty string (mismatch at col=0) |
| All identical strings | Returns the entire string |
Find the index of the first occurrence of pattern needle in string haystack. Return -1 if not found. If needle is empty, return 0.
Iterate through haystack, check if pattern matches at each position.
public int StrStr_Naive(string haystack, string needle) { if (needle.Length == 0) return 0; if (needle.Length > haystack.Length) return -1; for (int i = 0; i <= haystack.Length - needle.Length; i++) { int j; for (j = 0; j < needle.Length; j++) { if (haystack[i + j] != needle[j]) break; } if (j == needle.Length) return i; // Full match } return -1; }
Use a failure function to avoid redundant comparisons when a mismatch occurs.
public int StrStr_KMP(string haystack, string needle) { if (needle.Length == 0) return 0; // Build failure function (LPS array) int[] lps = new int[needle.Length]; for (int i = 1; i < needle.Length; i++) { int j = lps[i - 1]; while (j > 0 && needle[i] != needle[j]) { j = lps[j - 1]; } if (needle[i] == needle[j]) { lps[i] = j + 1; } } // KMP matching int k = 0; // needle pointer for (int i = 0; i < haystack.Length; i++) { while (k > 0 && haystack[i] != needle[k]) { k = lps[k - 1]; } if (haystack[i] == needle[k]) { k++; } if (k == needle.Length) { return i - needle.Length + 1; } } return -1; }
Input: haystack="hello", needle="ll"
2| Algorithm | Time (Best) | Time (Worst) | Space |
|---|---|---|---|
| Naive | O(n) | O(n * m) | O(1) |
| KMP | O(n + m) | O(n + m) | O(m) |
Given string s, return all possible ways to partition it into palindromic substrings.
Use backtracking to explore all partitions, pre-compute which substrings are palindromes to avoid repeated checks.
public IList<IList<string>> Partition(string s) { var result = new List<IList<string>>(); int n = s.Length; // DP table: isPalin[i,j] = true if s[i..j] is palindrome bool[,] isPalin = new bool[n, n]; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (s[i] == s[j] && (j - i <= 1 || isPalin[i + 1, j - 1])) { isPalin[i, j] = true; } } } // Backtracking void Backtrack(int start, List<string> current) { if (start == n) { result.Add(new List<string>(current)); return; } for (int end = start; end < n; end++) { if (isPalin[start, end]) { current.Add(s.Substring(start, end - start + 1)); Backtrack(end + 1, current); current.RemoveAt(current.Count - 1); } } } Backtrack(0, new List<string>()); return result; }
Input: "nitin"
[["n","i","t","i","n"], ["n","iti","n"]]| Aspect | Analysis |
|---|---|
| Time Complexity | O(n² + 2^n) — DP O(n²), backtracking O(2^n) |
| Space Complexity | O(n²) for DP table + O(n) recursion stack |
| Single character | Returns [["c"]] |
| All different chars | Only partitioning is individual characters |
| Entire string palindrome | Includes whole string as one partition option |
Given a digit string, count ways to decode it using mapping: 1='A', 2='B', ..., 26='Z'. For example, "12" can decode to "AB" (1,2) or "L" (12).
dp[i] = ways to decode s[0..i-1]. At each position, check if s[i-1] alone or s[i-2..i-1] together form valid codes.
public int NumDecodings(string s) { if (s.Length == 0 || s[0] == '0') return 0; int n = s.Length; long[] dp = new long[n + 1]; dp[0] = 1; // Empty string dp[1] = s[0] != '0' ? 1 : 0; for (int i = 2; i <= n; i++) { // Check single digit (s[i-1]) int oneDigit = s[i - 1] - '0'; if (oneDigit >= 1 && oneDigit <= 9) { dp[i] += dp[i - 1]; } // Check two digits (s[i-2..i-1]) int twoDigits = (int)(char.GetNumericValue(s[i - 2]) * 10 + char.GetNumericValue(s[i - 1])); if (twoDigits >= 10 && twoDigits <= 26) { dp[i] += dp[i - 2]; } } return (int)dp[n]; }
Input: "226"
3 (decodes: "2,2,6", "22,6", "2,26")| Aspect | Analysis |
|---|---|
| Time Complexity | O(n) — single pass through string |
| Space Complexity | O(n) for DP array (can optimize to O(1)) |
| Starts with '0' | Returns 0 (invalid) |
| Contains '0' in middle | Valid only if preceded by '1' or '2' |
| Ends with '0' | Valid only if previous digit is '1' or '2' |
| Single digit | Returns 1 if '1'-'9', else 0 |
Check if string s matches pattern p where '?' matches single character and '*' matches zero or more characters.
dp[i][j] = true if s[0..i-1] matches p[0..j-1]. Handle '*' by checking zero (dp[i][j-1]) or one+ (dp[i-1][j]) matches.
public bool IsMatch(string s, string p) { int sLen = s.Length, pLen = p.Length; bool[,] dp = new bool[sLen + 1, pLen + 1]; // Base case: empty string and empty pattern dp[0, 0] = true; // Handle patterns like *, **, a*b* (first row) for (int j = 1; j <= pLen; j++) { if (p[j - 1] == '*') { dp[0, j] = dp[0, j - 1]; } } // Fill the DP table for (int i = 1; i <= sLen; i++) { for (int j = 1; j <= pLen; j++) { char sChar = s[i - 1]; char pChar = p[j - 1]; if (pChar == '*') { // * matches zero chars (p[j-1] = *) or one+ chars (move s pointer) dp[i, j] = dp[i, j - 1] || dp[i - 1, j]; } else if (pChar == '?' || sChar == pChar) { // ? or exact match dp[i, j] = dp[i - 1, j - 1]; } // else: dp[i,j] remains false } } return dp[sLen, pLen]; }
Input: s="aa", p="*"
true| Aspect | Analysis |
|---|---|
| Time Complexity | O(m * n) where m=len(s), n=len(p) |
| Space Complexity | O(m * n) for DP table |
| Pattern '*' only | Matches any string (true) |
| Pattern with leading '*' | Handled by base case propagation |
| Multiple consecutive '*' | Treated as single '*' effectively |
| No wildcard | Requires exact match |
Given a string, return a reorganized version where no two adjacent characters are the same. If impossible, return empty string.
Always place the character with highest remaining frequency, ensuring it's not the same as the previous. If max-frequency char > (n+1)/2, it's impossible.
public string ReorganizeString(string s) { // Count character frequencies var freq = new Dictionary<char, int>(); int maxFreq = 0; foreach (char c in s) { if (!freq.ContainsKey(c)) freq[c] = 0; freq[c]++; maxFreq = Math.Max(maxFreq, freq[c]); } // If max frequency > (n+1)/2, impossible if (maxFreq > (s.Length + 1) / 2) return ""; // Max heap (priority queue) of (freq, char) var heap = new PriorityQueue<(int, char), int>(); foreach (var kvp in freq) { heap.Enqueue((kvp.Value, kvp.Key), -kvp.Value); } var result = new StringBuilder(); while (heap.Count > 0) { // Take two most frequent characters var (freq1, char1) = heap.Dequeue(); if (heap.Count == 0) { // Only one character left, can only use if freq=1 if (freq1 == 1) { result.Append(char1); } break; } var (freq2, char2) = heap.Dequeue(); // Add both characters result.Append(char1).Append(char2); // Decrease frequencies and re-enqueue if needed if (freq1 - 1 > 0) { heap.Enqueue((freq1 - 1, char1), -(freq1 - 1)); } if (freq2 - 1 > 0) { heap.Enqueue((freq2 - 1, char2), -(freq2 - 1)); } } return result.ToString(); }
Input: "aab"
"aba"| Aspect | Analysis |
|---|---|
| Time Complexity | O(n log k) where k=alphabet size |
| Space Complexity | O(k) for freq map and heap |
| Single character | Returns that character |
| All same character | Returns "" if length > 1, else the character |
| Two characters, equal freq | Always possible: "ababab..." |
Given strings s and t, return the minimum window substring in s that contains all characters in t. If no such window exists, return empty string.
public string MinWindow(string s, string t) { if (s.Length < t.Length) return ""; // Build target frequency map var targetFreq = new Dictionary<char, int>(); foreach (char c in t) { if (!targetFreq.ContainsKey(c)) targetFreq[c] = 0; targetFreq[c]++; } // Sliding window with window frequency map var windowFreq = new Dictionary<char, int>(); int required = targetFreq.Count; // Unique chars needed int formed = 0; // Unique chars with correct frequency int left = 0, minLen = int.MaxValue, minStart = 0; for (int right = 0; right < s.Length; right++) { char c = s[right]; // Add character to window if (!windowFreq.ContainsKey(c)) windowFreq[c] = 0; windowFreq[c]++; // Check if this character's frequency is now satisfied if (targetFreq.ContainsKey(c) && windowFreq[c] == targetFreq[c]) { formed++; } // Contract window from left while (left <= right && formed == required) { // Update minimum if current window is smaller if (right - left + 1 < minLen) { minLen = right - left + 1; minStart = left; } // Remove character from left char leftChar = s[left]; windowFreq[leftChar]--; // Check if we lost a required character if (targetFreq.ContainsKey(leftChar) && windowFreq[leftChar] < targetFreq[leftChar]) { formed--; } left++; } } return minLen == int.MaxValue ? "" : s.Substring(minStart, minLen); }
Input: s="ADOBECODEBANC", t="ABC"
"BANC"| Aspect | Analysis |
|---|---|
| Time Complexity | O(m + n) where m=len(s), n=len(t); each char visited twice |
| Space Complexity | O(n) for frequency maps (at most 52 chars) |
| No valid window | Returns empty string |
| Duplicate chars in target | Correctly counts required frequency |
| Window length = target length | Finds minimum containing substring |
| Case sensitivity | 'A' and 'a' treated as different characters |
| Problem | Primary Technique | Time Complexity | Space Complexity |
|---|---|---|---|
| Valid Palindrome | Two Pointers | O(n) | O(1) |
| Longest Palindromic Substring | Expand Around Center | O(n²) | O(1) |
| Reverse String | Two Pointers Swap | O(n) | O(1) |
| String to Integer (atoi) | Character Parsing | O(n) | O(1) |
| Count and Say | Simulation | O(n*m) | O(m) |
| Longest Common Prefix | Vertical Scan | O(n*m) | O(1) |
| Implement strStr | KMP / Naive | O(n+m) | O(m) |
| Palindrome Partitioning | Backtracking + DP | O(n² + 2^n) | O(n²) |
| Decode Ways | Dynamic Programming | O(n) | O(n) |
| Wildcard Matching | Dynamic Programming | O(m*n) | O(m*n) |
| Reorganize String | Frequency + Greedy | O(n log k) | O(k) |
| Minimum Window Substring | Sliding Window | O(m+n) | O(k) |