Beginner LevelData Structures & Algorithms
How do you reverse a string and check if two strings are anagrams?
ā Interview Prompt: Implement string reversal in O(N) and an anagram checker, discussing multiple approaches and their time/space complexities.
String Reversal:
ā¢
Swap characters using two pointers from both ends: $O(N)$ time, $O(1)$ extra space (in-place on a char array).
Anagram Check:
Two strings are anagrams if they contain the same characters with the same frequencies.
ā¢
Sort approach: Sort both strings and compare ā $O(N \log N)$.
ā¢
Frequency map: Count character frequencies ā $O(N)$ time, $O(1)$ space (bounded by 26 alphabets).
Code Implementation Example
typescript
// String reversal ā O(N)
function reverseString(s: string): string {
const arr = s.split('');
let l = 0, r = arr.length - 1;
while (l < r) {
[arr[l], arr[r]] = [arr[r], arr[l]];
l++; r--;
}
return arr.join('');
}
// Anagram check ā O(N) with frequency map
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false;
const freq: Record<string, number> = {};
for (const c of s) freq[c] = (freq[c] ?? 0) + 1;
for (const c of t) {
if (!freq[c]) return false;
freq[c]--;
}
return true;
}š”O(N) string reversal and anagram detection using frequency maps.
šÆ Interview Key Takeaway
String problems often reduce to frequency counting or two-pointer traversal. Always clarify character set constraints (ASCII vs Unicode).
#DSA#Strings#Anagram#Two Pointers#Beginner
Back to all Data Structures & Algorithms Questionsā