cpp
exercises
exercises.cpp⚙️cpp
/**
* C++ Strings - Exercises
*
* Practice problems to reinforce understanding of C++ strings.
* Each exercise includes a description, TODO section, and hints.
* Complete solutions are provided in the ANSWER KEY at the bottom.
*
* Difficulty Levels:
* ⭐ - Beginner
* ⭐⭐ - Intermediate
* ⭐⭐⭐ - Advanced
*
* Compile: g++ -std=c++17 -Wall -Wextra exercises.cpp -o exercises
* Run: ./exercises
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cctype>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// ============================================================
// Exercise 1: Reverse String ⭐
// ============================================================
/**
* Reverse a string in place.
*
* Examples:
* reverse("hello") returns "olleh"
* reverse("A") returns "A"
*/
string reverseString(string s) {
// TODO: Reverse the string
// Hint: Use two pointers from both ends
// Hint: Or use std::reverse
return s; // Replace with your implementation
}
// ============================================================
// Exercise 2: Is Palindrome ⭐
// ============================================================
/**
* Check if a string is a palindrome (reads same forwards and backwards).
* Consider only alphanumeric characters and ignore case.
*
* Examples:
* isPalindrome("A man, a plan, a canal: Panama") returns true
* isPalindrome("race a car") returns false
*/
bool isPalindrome(const string& s) {
// TODO: Check if string is a palindrome
// Hint: Filter alphanumeric, convert to lowercase
// Hint: Compare from both ends
return false; // Replace with your implementation
}
// ============================================================
// Exercise 3: First Unique Character ⭐
// ============================================================
/**
* Find the index of the first non-repeating character.
* Return -1 if no such character exists.
*
* Examples:
* firstUnique("leetcode") returns 0 ('l')
* firstUnique("loveleetcode") returns 2 ('v')
* firstUnique("aabb") returns -1
*/
int firstUnique(const string& s) {
// TODO: Find first unique character
// Hint: Use a hash map to count occurrences
// Hint: Iterate again to find first with count 1
return -1; // Replace with your implementation
}
// ============================================================
// Exercise 4: Valid Anagram ⭐
// ============================================================
/**
* Check if two strings are anagrams of each other.
* Anagrams use the same characters with the same frequency.
*
* Examples:
* isAnagram("anagram", "nagaram") returns true
* isAnagram("rat", "car") returns false
*/
bool isAnagram(const string& s, const string& t) {
// TODO: Check if s and t are anagrams
// Hint: Sort both and compare
// Hint: Or use character frequency count
return false; // Replace with your implementation
}
// ============================================================
// Exercise 5: String Compression ⭐⭐
// ============================================================
/**
* Compress a string using counts of repeated characters.
* If compressed is not shorter, return original.
*
* Examples:
* compress("aabcccccaaa") returns "a2b1c5a3"
* compress("abc") returns "abc" (compressed "a1b1c1" is longer)
*/
string compress(const string& s) {
// TODO: Compress the string
// Hint: Iterate and count consecutive chars
// Hint: Build result string, compare lengths
return s; // Replace with your implementation
}
// ============================================================
// Exercise 6: Longest Common Prefix ⭐⭐
// ============================================================
/**
* Find the longest common prefix among an array of strings.
*
* Examples:
* longestPrefix({"flower", "flow", "flight"}) returns "fl"
* longestPrefix({"dog", "racecar", "car"}) returns ""
*/
string longestPrefix(const vector<string>& strs) {
// TODO: Find longest common prefix
// Hint: Compare character by character
// Hint: Stop when mismatch or end of any string
return ""; // Replace with your implementation
}
// ============================================================
// Exercise 7: Group Anagrams ⭐⭐
// ============================================================
/**
* Group strings that are anagrams of each other.
*
* Examples:
* groupAnagrams({"eat","tea","tan","ate","nat","bat"})
* returns {{"bat"}, {"nat","tan"}, {"ate","eat","tea"}}
*/
vector<vector<string>> groupAnagrams(const vector<string>& strs) {
// TODO: Group anagrams together
// Hint: Use sorted string as key in hash map
// Hint: Collect all strings with same sorted key
return {}; // Replace with your implementation
}
// ============================================================
// Exercise 8: Longest Substring Without Repeating ⭐⭐
// ============================================================
/**
* Find the length of the longest substring without repeating characters.
*
* Examples:
* lengthOfLongestSubstring("abcabcbb") returns 3 ("abc")
* lengthOfLongestSubstring("bbbbb") returns 1 ("b")
* lengthOfLongestSubstring("pwwkew") returns 3 ("wke")
*/
int lengthOfLongestSubstring(const string& s) {
// TODO: Find length of longest substring without repeats
// Hint: Use sliding window technique
// Hint: Use set or map to track characters in window
return 0; // Replace with your implementation
}
// ============================================================
// Exercise 9: String to Integer (atoi) ⭐⭐⭐
// ============================================================
/**
* Implement atoi which converts a string to an integer.
* Rules:
* - Discard leading whitespace
* - Optional +/- sign
* - Read digits until non-digit
* - Clamp to INT_MIN/INT_MAX on overflow
* - Return 0 if no valid conversion
*
* Examples:
* myAtoi("42") returns 42
* myAtoi(" -42") returns -42
* myAtoi("4193 with words") returns 4193
* myAtoi("-91283472332") returns -2147483648 (INT_MIN)
*/
int myAtoi(const string& s) {
// TODO: Implement atoi
// Hint: Skip whitespace, handle sign
// Hint: Read digits, check for overflow before multiply/add
return 0; // Replace with your implementation
}
// ============================================================
// Exercise 10: Minimum Window Substring ⭐⭐⭐
// ============================================================
/**
* Find the minimum window in s that contains all characters of t.
* Return empty string if no such window exists.
*
* Examples:
* minWindow("ADOBECODEBANC", "ABC") returns "BANC"
* minWindow("a", "a") returns "a"
* minWindow("a", "aa") returns ""
*/
string minWindow(const string& s, const string& t) {
// TODO: Find minimum window substring
// Hint: Use sliding window with two pointers
// Hint: Use frequency map for characters needed
// Hint: Expand right to include chars, contract left to minimize
return ""; // Replace with your implementation
}
// ============================================================
// BONUS Exercise: Edit Distance ⭐⭐⭐
// ============================================================
/**
* Find minimum number of operations to convert word1 to word2.
* Operations: insert, delete, replace a character.
*
* Examples:
* editDistance("horse", "ros") returns 3
* editDistance("intention", "execution") returns 5
*/
int editDistance(const string& word1, const string& word2) {
// TODO: Find minimum edit distance
// Hint: Use dynamic programming
// Hint: dp[i][j] = min edits to convert word1[0..i-1] to word2[0..j-1]
// Hint: Consider: insert, delete, replace or match
return 0; // Replace with your implementation
}
// ============================================================
// Test Functions
// ============================================================
void testExercise1() {
cout << "\n=== Testing Exercise 1: Reverse String ===" << endl;
cout << "reverseString(\"hello\") = \"" << reverseString("hello") << "\" (expected: \"olleh\")" << endl;
cout << "reverseString(\"A\") = \"" << reverseString("A") << "\" (expected: \"A\")" << endl;
cout << "reverseString(\"\") = \"" << reverseString("") << "\" (expected: \"\")" << endl;
}
void testExercise2() {
cout << "\n=== Testing Exercise 2: Is Palindrome ===" << endl;
cout << boolalpha;
cout << "isPalindrome(\"A man, a plan, a canal: Panama\") = " << isPalindrome("A man, a plan, a canal: Panama") << " (expected: true)" << endl;
cout << "isPalindrome(\"race a car\") = " << isPalindrome("race a car") << " (expected: false)" << endl;
cout << "isPalindrome(\" \") = " << isPalindrome(" ") << " (expected: true)" << endl;
}
void testExercise3() {
cout << "\n=== Testing Exercise 3: First Unique ===" << endl;
cout << "firstUnique(\"leetcode\") = " << firstUnique("leetcode") << " (expected: 0)" << endl;
cout << "firstUnique(\"loveleetcode\") = " << firstUnique("loveleetcode") << " (expected: 2)" << endl;
cout << "firstUnique(\"aabb\") = " << firstUnique("aabb") << " (expected: -1)" << endl;
}
void testExercise4() {
cout << "\n=== Testing Exercise 4: Valid Anagram ===" << endl;
cout << boolalpha;
cout << "isAnagram(\"anagram\", \"nagaram\") = " << isAnagram("anagram", "nagaram") << " (expected: true)" << endl;
cout << "isAnagram(\"rat\", \"car\") = " << isAnagram("rat", "car") << " (expected: false)" << endl;
}
void testExercise5() {
cout << "\n=== Testing Exercise 5: String Compression ===" << endl;
cout << "compress(\"aabcccccaaa\") = \"" << compress("aabcccccaaa") << "\" (expected: \"a2b1c5a3\")" << endl;
cout << "compress(\"abc\") = \"" << compress("abc") << "\" (expected: \"abc\")" << endl;
}
void testExercise6() {
cout << "\n=== Testing Exercise 6: Longest Common Prefix ===" << endl;
cout << "longestPrefix({\"flower\",\"flow\",\"flight\"}) = \"" << longestPrefix({"flower","flow","flight"}) << "\" (expected: \"fl\")" << endl;
cout << "longestPrefix({\"dog\",\"racecar\",\"car\"}) = \"" << longestPrefix({"dog","racecar","car"}) << "\" (expected: \"\")" << endl;
}
void testExercise7() {
cout << "\n=== Testing Exercise 7: Group Anagrams ===" << endl;
auto result = groupAnagrams({"eat","tea","tan","ate","nat","bat"});
cout << "groupAnagrams({\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"}):" << endl;
for (const auto& group : result) {
cout << " [";
for (size_t i = 0; i < group.size(); i++) {
cout << "\"" << group[i] << "\"";
if (i < group.size() - 1) cout << ", ";
}
cout << "]" << endl;
}
cout << "(expected: groups like {bat}, {nat,tan}, {ate,eat,tea})" << endl;
}
void testExercise8() {
cout << "\n=== Testing Exercise 8: Longest Substring Without Repeating ===" << endl;
cout << "lengthOfLongestSubstring(\"abcabcbb\") = " << lengthOfLongestSubstring("abcabcbb") << " (expected: 3)" << endl;
cout << "lengthOfLongestSubstring(\"bbbbb\") = " << lengthOfLongestSubstring("bbbbb") << " (expected: 1)" << endl;
cout << "lengthOfLongestSubstring(\"pwwkew\") = " << lengthOfLongestSubstring("pwwkew") << " (expected: 3)" << endl;
}
void testExercise9() {
cout << "\n=== Testing Exercise 9: String to Integer (atoi) ===" << endl;
cout << "myAtoi(\"42\") = " << myAtoi("42") << " (expected: 42)" << endl;
cout << "myAtoi(\" -42\") = " << myAtoi(" -42") << " (expected: -42)" << endl;
cout << "myAtoi(\"4193 with words\") = " << myAtoi("4193 with words") << " (expected: 4193)" << endl;
cout << "myAtoi(\"words and 987\") = " << myAtoi("words and 987") << " (expected: 0)" << endl;
}
void testExercise10() {
cout << "\n=== Testing Exercise 10: Minimum Window Substring ===" << endl;
cout << "minWindow(\"ADOBECODEBANC\", \"ABC\") = \"" << minWindow("ADOBECODEBANC", "ABC") << "\" (expected: \"BANC\")" << endl;
cout << "minWindow(\"a\", \"a\") = \"" << minWindow("a", "a") << "\" (expected: \"a\")" << endl;
cout << "minWindow(\"a\", \"aa\") = \"" << minWindow("a", "aa") << "\" (expected: \"\")" << endl;
}
void testBonus() {
cout << "\n=== Testing BONUS: Edit Distance ===" << endl;
cout << "editDistance(\"horse\", \"ros\") = " << editDistance("horse", "ros") << " (expected: 3)" << endl;
cout << "editDistance(\"intention\", \"execution\") = " << editDistance("intention", "execution") << " (expected: 5)" << endl;
}
// ============================================================
// Main Function
// ============================================================
int main() {
cout << "╔════════════════════════════════════════════════════════════╗" << endl;
cout << "║ C++ STRINGS - EXERCISES ║" << endl;
cout << "╚════════════════════════════════════════════════════════════╝" << endl;
testExercise1();
testExercise2();
testExercise3();
testExercise4();
testExercise5();
testExercise6();
testExercise7();
testExercise8();
testExercise9();
testExercise10();
testBonus();
cout << "\n╔════════════════════════════════════════════════════════════╗" << endl;
cout << "║ Complete the TODO sections and re-run! ║" << endl;
cout << "╚════════════════════════════════════════════════════════════╝" << endl;
return 0;
}
// ============================================================
// ANSWER KEY
// ============================================================
/*
// Exercise 1: Reverse String
string reverseString(string s) {
int left = 0, right = s.size() - 1;
while (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
return s;
}
// Exercise 2: Is Palindrome
bool isPalindrome(const string& s) {
int left = 0, right = s.size() - 1;
while (left < right) {
// Skip non-alphanumeric
while (left < right && !isalnum(s[left])) left++;
while (left < right && !isalnum(s[right])) right--;
if (tolower(s[left]) != tolower(s[right])) {
return false;
}
left++;
right--;
}
return true;
}
// Exercise 3: First Unique Character
int firstUnique(const string& s) {
unordered_map<char, int> count;
for (char c : s) {
count[c]++;
}
for (int i = 0; i < s.size(); i++) {
if (count[s[i]] == 1) {
return i;
}
}
return -1;
}
// Exercise 4: Valid Anagram
bool isAnagram(const string& s, const string& t) {
if (s.size() != t.size()) return false;
int count[26] = {0};
for (int i = 0; i < s.size(); i++) {
count[s[i] - 'a']++;
count[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (count[i] != 0) return false;
}
return true;
}
// Exercise 5: String Compression
string compress(const string& s) {
if (s.empty()) return s;
string result;
int count = 1;
for (size_t i = 1; i <= s.size(); i++) {
if (i < s.size() && s[i] == s[i-1]) {
count++;
} else {
result += s[i-1];
result += to_string(count);
count = 1;
}
}
return result.size() < s.size() ? result : s;
}
// Exercise 6: Longest Common Prefix
string longestPrefix(const vector<string>& strs) {
if (strs.empty()) return "";
string prefix = strs[0];
for (size_t i = 1; i < strs.size(); i++) {
while (strs[i].find(prefix) != 0) {
prefix = prefix.substr(0, prefix.size() - 1);
if (prefix.empty()) return "";
}
}
return prefix;
}
// Exercise 7: Group Anagrams
vector<vector<string>> groupAnagrams(const vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (const string& s : strs) {
string key = s;
sort(key.begin(), key.end());
groups[key].push_back(s);
}
vector<vector<string>> result;
for (auto& pair : groups) {
result.push_back(pair.second);
}
return result;
}
// Exercise 8: Longest Substring Without Repeating
int lengthOfLongestSubstring(const string& s) {
unordered_set<char> chars;
int left = 0, maxLen = 0;
for (int right = 0; right < s.size(); right++) {
while (chars.count(s[right])) {
chars.erase(s[left]);
left++;
}
chars.insert(s[right]);
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
// Exercise 9: String to Integer (atoi)
int myAtoi(const string& s) {
int i = 0, n = s.size();
// Skip whitespace
while (i < n && s[i] == ' ') i++;
if (i == n) return 0;
// Handle sign
int sign = 1;
if (s[i] == '-' || s[i] == '+') {
sign = (s[i] == '-') ? -1 : 1;
i++;
}
// Read digits
long result = 0;
while (i < n && isdigit(s[i])) {
result = result * 10 + (s[i] - '0');
// Check overflow
if (sign * result > INT_MAX) return INT_MAX;
if (sign * result < INT_MIN) return INT_MIN;
i++;
}
return sign * result;
}
// Exercise 10: Minimum Window Substring
string minWindow(const string& s, const string& t) {
if (s.empty() || t.empty() || s.size() < t.size()) return "";
unordered_map<char, int> need, have;
for (char c : t) need[c]++;
int required = need.size();
int formed = 0;
int left = 0;
int minLen = INT_MAX;
int minStart = 0;
for (int right = 0; right < s.size(); right++) {
char c = s[right];
have[c]++;
if (need.count(c) && have[c] == need[c]) {
formed++;
}
while (formed == required) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
char leftChar = s[left];
have[leftChar]--;
if (need.count(leftChar) && have[leftChar] < need[leftChar]) {
formed--;
}
left++;
}
}
return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
}
// BONUS: Edit Distance
int editDistance(const string& word1, const string& word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// Base cases
for (int i = 0; i <= m; i++) dp[i][0] = i; // Delete all
for (int j = 0; j <= n; j++) dp[0][j] = j; // Insert all
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1]; // Characters match
} else {
dp[i][j] = 1 + min({
dp[i-1][j], // Delete from word1
dp[i][j-1], // Insert into word1
dp[i-1][j-1] // Replace
});
}
}
}
return dp[m][n];
}
*/