Java String Manipulation: Reverse, Palindrome, Anagram

1. The Foundation: String Traversal in Java

Before tackling specific problems, we must master the fundamental skill of processing a string character by character. In Java, strings are immutable, meaning they cannot be changed after creation. Therefore, most "manipulation" tasks involve creating a new string from the characters of the original.

The most common way to do this is to iterate through the string using a for loop and the charAt(i) method to access each character at its index. This simple pattern is the heart of countless string algorithms.

The following video from Simply Coding provides an excellent overview of this core template and how it can be adapted for various simple tasks like printing, counting, or selectively building new strings.

2. Problem 1: Reversing a String

Our first manipulation task is reversing a string. For example, "Java" becomes "avaJ".

Simple Approach: Building a New String

Using the traversal template we just learned, the most intuitive way to reverse a string is to iterate through the original string and prepend each character to a new, empty string.

Let's see this in action. For the string "BABAD":

1. Start with reversed = ""
2. Read 'B': reversed = "B" + reversed -> "B"
3. Read 'A': reversed = "A" + reversed -> "AB"
4. Read 'B': reversed = "B" + reversed -> "BAB"
5. Read 'A': reversed = "A" + reversed -> "ABAB"
6. Read 'D': reversed = "D" + reversed -> "DABAB"

The Simply Coding video you just watched demonstrates this exact logic.

In Java, while this works, concatenating strings in a loop can be inefficient because it creates a new string object in every iteration. A more idiomatic and performant way is to use the StringBuilder class, which is mutable: new StringBuilder(s).reverse().toString(). However, understanding the manual loop is crucial for interviews, as it demonstrates your grasp of the underlying process.

3. Problem 2: Checking for Palindromes

A palindrome is a string that reads the same forwards and backward, ignoring case and non-alphanumeric characters. For example, "A man, a plan, a canal: Panama" is a palindrome.

Brute-Force Approach: Clean, Reverse, and Compare

The most direct solution follows from our previous task:

1. Create a "clean" version of the string by removing non-alphanumeric characters and converting it to lowercase.
2. Reverse this clean string.
3. Compare the clean string with its reversed version. If they are identical, it's a palindrome.

This approach is correct and easy to understand, but it requires extra memory to store the new clean and reversed strings.

Optimal Approach: The Two-Pointer Technique

To achieve a more optimal solution with $O(1)$ space complexity, we must avoid creating new strings and work "in-place." This is a perfect scenario for the two-pointer technique.

The logic is as follows:

1. Place one pointer (left) at the beginning of the string and another (right) at the end.
2. Move the pointers toward each other (left++, right--).
3. At each step, check the characters at s[left] and s[right].
   • If a pointer is on a non-alphanumeric character, skip it by advancing that pointer inward and continuing.
   • Once both pointers are on valid characters, compare them (after converting to lowercase).
   • If they don't match, it's not a palindrome, so return false.
   • If they match, continue by moving both pointers inward.
4. If the pointers cross (left >= right) without finding any mismatches, the string is a palindrome.

This method is highly efficient as it performs a single pass over the string and uses constant extra space.

4. Problem 3: Checking for Anagrams

Two strings are anagrams if they contain the exact same characters with the same frequencies, but in a different order. For example, "anagram" and "nagaram" are anagrams.

"Better" Approach: Sorting

The definition of an anagram gives us a strong clue for our first improvement over a naive brute-force check. If two strings are anagrams, then when sorted alphabetically, they must become identical.

The algorithm is:

1. Check if the strings have different lengths. If so, they can't be anagrams.
2. Convert both strings to character arrays.
3. Sort both arrays.
4. Compare the sorted arrays. If they are equal, the original strings were anagrams.

This is a clean and clever solution. Its time complexity is dominated by the sorting step, which is typically $O(n\log n)$.

Optimal Approach: Frequency Counting (Array as a Hash Table)

Can we do better than $O(n\log n)$? Yes, by shifting our perspective from ordering to counting. Anagrams must have identical character frequency maps.

We can solve this in $O(n)$ time by counting character frequencies. If the character set is limited (e.g., only lowercase English letters, a common interview constraint), the most efficient way to do this is with a simple integer array of size 26.

The logic:

1. Again, check if the lengths are different and return false if they are.
2. Create an integer array counts of size 26, initialized to all zeros. This array will act as our frequency map.
3. Iterate through the first string (s). For each character, increment the corresponding counter in the counts array. (e.g., for 'c', increment counts[2]). You can get the index by using char - 'a'.
4. Iterate through the second string (t). For each character, decrement the corresponding counter.
5. After both loops, if the strings are anagrams, every counter in the counts array should have returned to zero. Iterate through the counts array; if you find any non-zero value, the strings are not anagrams.

This approach is optimal with $O(n)$ time complexity and $O(1)$ space complexity (since the array size is constant regardless of the input string length).

This video from Technosage provides a great walkthrough of this specific technique.

For a supplementary textual explanation, the NeetCode resource also covers this method excellently.

Conclusion

In this lesson, we established a solid foundation for working with strings. We began with the essential pattern of character-by-character traversal and applied it to solve three classic interview problems: string reversal, palindrome checking, and anagram detection.

Key Takeaways:

• String Traversal: A for loop with charAt(i) is the fundamental tool for most string algorithms in Java.
• Palindromes & Two Pointers: While a "reverse and compare" approach works, the two-pointer technique is the optimal, $O(1)$ space solution that demonstrates in-place manipulation skills.
• Anagrams & Frequency Counting: While sorting is a clever $O(n\log n)$ solution, using an array as a frequency map is the most optimal $O(n)$ time and $O(1)$ space solution for limited character sets.
• Progression is Key: For each problem, we saw a clear path from a simple but less efficient solution to a more optimized one—a thought process highly valued in technical interviews.

In our next lesson, we will build on these fundamentals to solve another common problem: finding the longest common prefix among an array of strings.