Sure!
Here are 20 problems each for easy, intermediate, and difficult levels that involve string
manipulation in Python:
### Easy
1. **Reverse a string.**
```python
def reverse_string(s):
return s[::-1]
```
2. **Check if a string is a palindrome.**
```python
def is_palindrome(s):
return s == s[::-1]
```
3. **Count the number of vowels in a string.**
```python
def count_vowels(s):
vowels = "aeiouAEIOU"
return sum(1 for char in s if char in vowels)
```
4. **Convert a string to uppercase.**
```python
def to_uppercase(s):
return s.upper()
```
5. **Remove all spaces from a string.**
```python
def remove_spaces(s):
return s.replace(" ", "")
```
6. **Check if a string contains only digits.**
```python
def is_digit(s):
return s.isdigit()
```
7. **Replace vowels in a string with a specific character.**
```python
def replace_vowels(s, ch):
vowels = "aeiouAEIOU"
for vowel in vowels:
s = s.replace(vowel, ch)
return s
```
8. **Find the length of a string.**
```python
def string_length(s):
return len(s)
```
9. **Count the occurrences of a substring in a string.**
```python
def count_substring(s, sub):
return s.count(sub)
```
10. **Convert a string to lowercase.**
```python
def to_lowercase(s):
return s.lower()
```
11. **Check if a string starts with a specific substring.**
```python
def starts_with(s, sub):
return s.startswith(sub)
```
12. **Check if a string ends with a specific substring.**
```python
def ends_with(s, sub):
return s.endswith(sub)
```
13. **Find the index of the first occurrence of a substring.**
```python
def find_substring(s, sub):
return s.find(sub)
```
14. **Split a string into a list of words.**
```python
def split_string(s):
return s.split()
```
15. **Join a list of words into a single string.**
```python
def join_words(words):
return " ".join(words)
```
16. **Capitalize the first letter of each word in a string.**
```python
def capitalize_words(s):
return s.title()
```
17. **Check if a string is a valid identifier.**
```python
def is_identifier(s):
return s.isidentifier()
```
18. **Remove a specific character from a string.**
```python
def remove_char(s, ch):
return s.replace(ch, "")
```
19. **Count the number of words in a string.**
```python
def count_words(s):
return len(s.split())
```
20. **Swap the case of all characters in a string.**
```python
def swap_case(s):
return s.swapcase()
```
### Intermediate
1. **Find all permutations of a string.**
```python
from itertools import permutations
def string_permutations(s):
return [''.join(p) for p in permutations(s)]
```
2. **Check if two strings are anagrams.**
```python
def are_anagrams(s1, s2):
return sorted(s1) == sorted(s2)
```
3. **Convert a string to title case without using title().**
```python
def to_title_case(s):
return ' '.join(word.capitalize() for word in s.split())
```
4. **Find the longest word in a string.**
```python
def longest_word(s):
words = s.split()
return max(words, key=len)
```
5. **Count the frequency of each character in a string.**
```python
from collections import Counter
def char_frequency(s):
return Counter(s)
```
6. **Remove duplicate characters from a string.**
```python
def remove_duplicates(s):
return ''.join(sorted(set(s), key=s.index))
```
7. **Check if a string is a valid palindrome, ignoring non-alphanumeric characters.**
```python
import re
def is_valid_palindrome(s):
s = re.sub(r'[^A-Za-z0-9]', '', s).lower()
return s == s[::-1]
```
8. **Sort the words in a string alphabetically.**
```python
def sort_words(s):
words = s.split()
words.sort()
return ' '.join(words)
```
9. **Find the first non-repeating character in a string.**
```python
def first_non_repeating_char(s):
count = Counter(s)
for char in s:
if count[char] == 1:
return char
return None
```
10. **Find the longest common prefix among a list of strings.**
```python
def longest_common_prefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while s[:len(prefix)] != prefix:
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
```
11. **Check if a string contains another string (without using the in keyword).**
```python
def contains_string(s, sub):
return s.find(sub) != -1
```
12. **Implement a basic Caesar cipher.**
```python
def caesar_cipher(s, shift):
result = ""
for char in s:
if char.isalpha():
shift_base = ord('a') if char.islower() else ord('A')
result += chr((ord(char) - shift_base + shift) % 26 + shift_base)
else:
result += char
return result
```
13. **Count the number of uppercase and lowercase letters in a string.**
```python
def count_case(s):
upper = sum(1 for char in s if char.isupper())
lower = sum(1 for char in s if char.islower())
return upper, lower
```
14. **Check if a string is a valid password (at least 8 characters, contains both letters and
numbers).**
```python
def is_valid_password(s):
if len(s) < 8:
return False
has_digit = any(char.isdigit() for char in s)
has_letter = any(char.isalpha() for char in s)
return has_digit and has_letter
```
15. **Convert a string to a number (integer or float) if possible.**
```python
def convert_to_number(s):
try:
return int(s)
except ValueError:
try:
return float(s)
except ValueError:
return None
```
16. **Find the second most frequent character in a string.**
```python
def second_most_frequent_char(s):
count = Counter(s)
most_common = count.most_common()
return most_common[1][0] if len(most_common) > 1 else None
```
17. **Replace all spaces with a given character.**
```python
def replace_spaces(s, ch):
return s.replace(" ", ch)
```
18. **Check if two strings are rotations of each other.**
```python
def are_rotations(s1, s2):
return len(s1) == len(s2) and s2 in (s1 + s1)
```
19. **Remove leading and trailing whitespaces from a string without using strip().**
```python
def remove_whitespaces(s):
start = 0
end = len(s) - 1
while start <= end and s[start] == ' ':
start += 1
while end >= start and s[end] == ' ':
end -= 1
return s[start:end+1]
```
20. **Find the longest palindrome substring in a string.**
```python
def longest_palindrome(s):
def expand_around_center(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right]
longest = ""
for i in range(len(s)):
odd_palindrome = expand_around_center(s, i, i)
even_palindrome = expand_around_center(s, i, i+1)
longest = max(longest, odd_palindrome, even_palindrome, key=len)
return longest
```
### Difficult
1. **Implement a function to find all the anagrams of a string within another string.**
```python
def find_anagrams(s, p):
from collections import Counter
result = []
p_count = Counter(p)
s_count = Counter(s[:len(p)-1])
for i in range(len(p)-1, len(s)):
s_count[s[i]]
+= 1
if s_count == p_count:
result.append(i-len(p)+1)
s_count[s[i-len(p)+1]] -= 1
if s_count[s[i-len(p)+1]] == 0:
del s_count[s[i-len(p)+1]]
return result
```
2. **Implement a basic text justification algorithm.**
```python
def justify_text(words, max_width):
res, cur, num_of_letters = [], [], 0
for w in words:
if num_of_letters + len(w) + len(cur) > max_width:
for i in range(max_width - num_of_letters):
cur[i % (len(cur) - 1 or 1)] += ' '
res.append(''.join(cur))
cur, num_of_letters = [], 0
cur += [w]
num_of_letters += len(w)
return res + [' '.join(cur).ljust(max_width)]
```
3. **Implement a function to find the smallest window in a string containing all characters of
another string.**
```python
def min_window(s, t):
from collections import Counter
if not t or not s:
return ""
dict_t = Counter(t)
required = len(dict_t)
l, r = 0, 0
formed = 0
window_counts = {}
ans = float("inf"), None, None
while r < len(s):
char = s[r]
window_counts[char] = window_counts.get(char, 0) + 1
if char in dict_t and window_counts[char] == dict_t[char]:
formed += 1
while l <= r and formed == required:
char = s[l]
if r - l + 1 < ans[0]:
ans = (r - l + 1, l, r)
window_counts[char] -= 1
if char in dict_t and window_counts[char] < dict_t[char]:
formed -= 1
l += 1
r += 1
return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]
```
4. **Implement a function to determine the edit distance between two strings.**
```python
def edit_distance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
```
5. **Implement a function to convert a string to a Zigzag pattern on a given number of rows.**
```python
def convert_zigzag(s, num_rows):
if num_rows == 1 or num_rows >= len(s):
return s
res = [''] * num_rows
index, step = 0, 1
for char in s:
res[index] += char
if index == 0:
step = 1
elif index == num_rows - 1:
step = -1
index += step
return ''.join(res)
```
6. **Implement a function to decode a string encoded with a given pattern.**
```python
def decode_string(s):
stack = []
current_string = ""
k=0
for char in s:
if char.isdigit():
k = k * 10 + int(char)
elif char == '[':
stack.append((current_string, k))
current_string, k = "", 0
elif char == ']':
last_string, last_k = stack.pop()
current_string = last_string + last_k * current_string
else:
current_string += char
return current_string
```
7. **Implement a function to check if a string matches a given pattern (with '.' and '*').**
```python
def is_match(text, pattern):
dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]
dp[0][0] = True
for i in range(1, len(pattern) + 1):
if pattern[i-1] == '*':
dp[0][i] = dp[0][i-2]
for i in range(1, len(text) + 1):
for j in range(1, len(pattern) + 1):
if pattern[j-1] in {text[i-1], '.'}:
dp[i][j] = dp[i-1][j-1]
elif pattern[j-1] == '*':
dp[i][j] = dp[i][j-2] or (pattern[j-2] in {text[i-1], '.'} and dp[i-1][j])
return dp[-1][-1]
```
8. **Implement a function to evaluate a reverse Polish notation expression.**
```python
def eval_rpn(tokens):
stack = []
for token in tokens:
if token not in "+-*/":
stack.append(int(token))
else:
b, a = stack.pop(), stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
else:
stack.append(int(a / b))
return stack[0]
```
9. **Implement a function to find the longest substring with at most two distinct characters.**
```python
def length_of_longest_substring_two_distinct(s):
from collections import defaultdict
if len(s) < 3:
return len(s)
left, right = 0, 0
hashmap = defaultdict()
max_len = 2
while right < len(s):
if len(hashmap) < 3:
hashmap[s[right]] = right
right += 1
if len(hashmap) == 3:
del_idx = min(hashmap.values())
del hashmap[s[del_idx]]
left = del_idx + 1
max_len = max(max_len, right - left)
return max_len
```
10. **Implement a function to find the longest substring without repeating characters.**
```python
def length_of_longest_substring(s):
char_index = {}
left = max_len = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
```
11. **Implement a function to find all starting indices of substring(s) in s that is a concatenation of
each word in words exactly once and without any intervening characters.**
```python
def find_substring(s, words):
from collections import Counter
if not s or not words:
return []
word_len, num_words = len(words[0]), len(words)
word_count = Counter(words)
total_len = word_len * num_words
res = []
for i in range(word_len):
left = i
cur_count = Counter()
count = 0
for j in range(i, len(s) - word_len + 1, word_len):
word = s[j:j + word_len]
if word in word_count:
cur_count[word] += 1
count += 1
while cur_count[word] > word_count[word]:
cur_count[s[left:left + word_len]] -= 1
count -= 1
left += word_len
if count == num_words:
res.append(left)
else:
cur_count.clear()
count = 0
left = j + word_len
return res
```
12. **Implement a function to determine if a string can be segmented into a space-separated
sequence of one or more dictionary words.**
```python
def word_break(s, word_dict):
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_dict:
dp[i] = True
break
return dp[-1]
```
13. **Implement a function to check if a given string is an interleaving of two other strings.**
```python
def is_interleave(s1, s2, s3):
if len(s1) + len(s2) != len(s3):
return False
dp = [[False] * (len(s2) + 1) for _ in range(len(s1) +
1)]
dp[0][0] = True
for i in range(1, len(s1) + 1):
dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
for j in range(1, len(s2) + 1):
dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
return dp[-1][-1]
```
14. **Implement a function to find the longest substring with at most k distinct characters.**
```python
def length_of_longest_substring_k_distinct(s, k):
from collections import defaultdict
if k == 0:
return 0
left, right = 0, 0
hashmap = defaultdict()
max_len = 0
while right < len(s):
hashmap[s[right]] = right
right += 1
if len(hashmap) > k:
del_idx = min(hashmap.values())
del hashmap[s[del_idx]]
left = del_idx + 1
max_len = max(max_len, right - left)
return max_len
```
15. **Implement a function to check if a string can be constructed by taking a substring of it and
appending multiple copies of the substring together.**
```python
def repeated_substring_pattern(s):
return (s + s)[1:-1].find(s) != -1
```
16. **Implement a function to find all valid IP addresses from a given string.**
```python
def restore_ip_addresses(s):
def is_valid(segment):
return len(segment) == 1 or (segment[0] != '0' and int(segment) <= 255)
res = []
for i in range(1, min(4, len(s))):
for j in range(i+1, min(i+4, len(s))):
for k in range(j+1, min(j+4, len(s))):
if is_valid(s[:i]) and is_valid(s[i:j]) and is_valid(s[j:k]) and is_valid(s[k:]):
res.append(f"{s[:i]}.{s[i:j]}.{s[j:k]}.{s[k:]}")
return res
```
17. **Implement a function to remove invalid parentheses from a string.**
```python
def remove_invalid_parentheses(s):
def is_valid(s):
count = 0
for char in s:
if char == '(':
count += 1
elif char == ')':
count -= 1
if count < 0:
return False
return count == 0
level = {s}
while True:
valid = list(filter(is_valid, level))
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
```
18. **Implement a function to convert a string to an integer.**
```python
def string_to_integer(s):
s = s.strip()
if not s:
return 0
negative = False
if s[0] == '-':
negative = True
s = s[1:]
elif s[0] == '+':
s = s[1:]
result = 0
for char in s:
if not char.isdigit():
break
result = result * 10 + int(char)
result = -result if negative else result
return max(-2**31, min(result, 2**31-1))
```
19. **Implement a function to check if a string can be segmented into a space-separated sequence
of one or more dictionary words using Trie.**
```python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def word_break_trie(s, word_dict):
trie = Trie()
for word in word_dict:
trie.insert(word)
def can_break(start):
if start == len(s):
return True
node = trie.root
for i in range(start, len(s)):
if s[i] not in node.children:
return False
node = node.children[s[i]]
if node.is_end and can_break(i + 1):
return True
return False
return can_break(0)
```
20. **Implement a function to find the minimum number of characters to be inserted to form a
palindrome.**
```python
def min_insertions_palindrome(s):
def lcs(X, Y, m, n):
L = [[0] * (n + 1) for i in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]
rev = s[::-1]
n = len(s)
l = lcs(s, rev, n, n)
return n - l
```
These problems should provide a comprehensive set of challenges for learning and practicing string
manipulation in Python.
