What are common string manipulation problems in coding interviews?

String manipulation problems are quite common in coding interviews and test a candidate's understanding of various string operations, data structures, and algorithms. Here are some of the most common string manipulation problems you might encounter:

1. Reverse a String

Problem: Reverse the characters in a given string.

Solution:

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

# Alternatively, using a loop:
def reverse_string(s):
    return ''.join(reversed(s))

# Another way:
def reverse_string(s):
    return ''.join(s[i] for i in range(len(s) - 1, -1, -1))

2. Check if a String is a Palindrome

Problem: Determine if a given string is a palindrome (reads the same backward as forward).

Solution:

def is_palindrome(s):
    return s == s[::-1]

# Alternatively, using two pointers:
def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

3. Longest Palindromic Substring

Problem: Find the longest palindromic substring in a given string.

Solution:

def longest_palindromic_substring(s):
    n = len(s)
    if n < 2:
        return s
    
    start, max_len = 0, 1
    for i in range(1, n):
        even_palindrome = s[i-max_len:i+1]
        odd_palindrome = s[i-max_len-1:i+1]
        
        if i-max_len-1 >= 0 and odd_palindrome == odd_palindrome[::-1]:
            start = i-max_len-1
            max_len += 2
        elif even_palindrome == even_palindrome[::-1]:
            start = i-max_len
            max_len += 1
            
    return s[start:start+max_len]

4. Anagram Check

Problem: Determine if two strings are anagrams of each other.

Solution:

def are_anagrams(s1, s2):
    return sorted(s1) == sorted(s2)

# Alternatively, using a frequency counter:
from collections import Counter

def are_anagrams(s1, s2):
    return Counter(s1) == Counter(s2)

5. Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring without repeating characters.

Solution:

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

6. Count and Say

Problem: Generate the nth term in the count-and-say sequence.

Solution:

def count_and_say(n):
    if n == 1:
        return "1"
    
    prev_seq = count_and_say(n - 1)
    count = 1
    result = []
    
    for i in range(1, len(prev_seq)):
        if prev_seq[i] == prev_seq[i - 1]:
            count += 1
        else:
            result.append(str(count))
            result.append(prev_seq[i - 1])
            count = 1
    
    result.append(str(count))
    result.append(prev_seq[-1])
    
    return ''.join(result)

7. String to Integer (atoi)

Problem: Convert a string to an integer, handling edge cases as in the C atoi function.

Solution:

def my_atoi(s):
    s = s.strip()
    if not s:
        return 0
    
    negative = False
    if s[0] in ['-', '+']:
        if s[0] == '-':
            negative = True
        s = s[1:]
    
    result = 0
    for char in s:
        if not char.isdigit():
            break
        result = result * 10 + int(char)
    
    if negative:
        result = -result
    
    # Clamp to 32-bit signed integer range
    INT_MAX, INT_MIN = 2**31 - 1, -2**31
    if result < INT_MIN:
        return INT_MIN
    if result > INT_MAX:
        return INT_MAX
    
    return result

8. Longest Common Prefix

Problem: Find the longest common prefix string amongst an array of strings.

Solution:

def longest_common_prefix(strs):
    if not strs:
        return ""
    
    prefix = strs[0]
    for string in strs[1:]:
        while string[:len(prefix)] != prefix and prefix:
            prefix = prefix[:len(prefix)-1]
        if not prefix:
            break
    
    return prefix

9. Group Anagrams

Problem: Group a list of strings into anagram groups.

Solution:

from collections import defaultdict

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

10. Implement strStr()

Problem: Implement the strStr() function that finds the first occurrence of a substring in a string.

Solution:

def str_str(haystack, needle):
    if not needle:
        return 0
    if not haystack:
        return -1
    
    l, n = len(haystack), len(needle)
    for i in range(l - n + 1):
        if haystack[i:i+n] == needle:
            return i
    return -1

These problems cover a wide range of string manipulation techniques and are frequently encountered in coding interviews. Practicing these problems will help you build a strong foundation in string manipulation and improve your problem-solving skills.