String Manipulation in Java: A Comprehensive Guide for Developers
As a senior Java developer, I often encounter string manipulation challenges that test core programming skills. Strings are immutable in Java, which makes operations like reversing, checking palindromes, or counting characters both interesting and critical for efficient coding. In this blog post, I’ll dive into ten common string manipulation problems, providing detailed solutions without relying on built-in functions (where specified) and explaining the logic step-by-step. Each solution is implemented in Java, optimized for clarity and performance, and includes explanations to help developers of all levels understand the approach.
1. Reverse a String (No Built-in Functions)
Reversing a string without using built-in functions like StringBuilder.reverse() requires manual iteration over the characters. The idea is to swap characters from the start and end of the string, moving inward until the middle is reached.
Solution
We convert the string to a char array (since strings are immutable) and use two pointers to swap characters.
public class StringManipulation {
public static String reverseString(String str) {
if (str == null || str.isEmpty()) {
return str;
}
char[] charArray = str.toCharArray();
int left = 0;
int right = charArray.length - 1;
while (left < right) {
// Swap characters
char temp = charArray[left];
charArray[left] = charArray[right];
charArray[right] = temp;
left++;
right--;
}
return new String(charArray);
}
}
Explanation
- Convert the string to a
chararray to allow manipulation. - Use two pointers (
leftandright) starting from the ends of the array. - Swap characters at these positions and move the pointers inward.
- Convert the modified array back to a string.
- Time Complexity: O(n), where n is the string length.
- Space Complexity: O(n) due to the char array.
Example: Input: "hello" → Output: "olleh"
2. Check if a String is a Palindrome
A palindrome is a string that reads the same forward and backward (e.g., "radar"). We’ll check this by comparing characters from both ends.
Solution
public static boolean isPalindrome(String str) {
if (str == null || str.isEmpty()) {
return true;
}
str = str.toLowerCase(); // Case-insensitive comparison
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
Explanation
- Handle null or empty strings as valid palindromes.
- Convert the string to lowercase for case-insensitive comparison.
- Use two pointers to compare characters from the start and end.
- If any mismatch occurs, return
false. If the loop completes, it’s a palindrome. - Time Complexity: O(n).
- Space Complexity: O(1) since we’re not using extra space (excluding input).
Example: Input: "Radar" → Output: true
3. Count Vowels and Consonants in a String
To count vowels and consonants, we iterate through the string and check each character against a set of vowels (a, e, i, o, u).
Solution
public static void countVowelsAndConsonants(String str) {
if (str == null || str.isEmpty()) {
System.out.println("Vowels: 0, Consonants: 0");
return;
}
str = str.toLowerCase();
int vowels = 0, consonants = 0;
for (char c : str.toCharArray()) {
if (Character.isLetter(c)) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
vowels++;
} else {
consonants++;
}
}
}
System.out.println("Vowels: " + vowels + ", Consonants: " + consonants);
}
Explanation
- Convert the string to lowercase to simplify vowel checking.
- Iterate through each character and check if it’s a letter.
- Increment
vowelsfor a, e, i, o, u; otherwise, incrementconsonantsfor other letters. - Ignore non-letter characters (e.g., spaces, punctuation).
- Time Complexity: O(n).
- Space Complexity: O(1).
Example: Input: "Hello World" → Output: Vowels: 3, Consonants: 5
4. Count Frequency of Each Character
To count the frequency of each character, we can use a fixed-size array (assuming ASCII characters) to store counts.
Solution
public static void countCharacterFrequency(String str) {
if (str == null || str.isEmpty()) {
System.out.println("Empty string");
return;
}
int[] frequency = new int[256]; // ASCII size
for (char c : str.toCharArray()) {
frequency[c]++;
}
for (int i = 0; i < 256; i++) {
if (frequency[i] > 0) {
System.out.println("'" + (char)i + "': " + frequency[i]);
}
}
}
Explanation
- Use an array of size 256 to cover all ASCII characters.
- Increment the count for each character’s ASCII value.
- Print only characters with non-zero frequency.
- Time Complexity: O(n) for counting, O(1) for printing (fixed ASCII size).
- Space Complexity: O(1) due to fixed array size.
Example: Input: "banana" → Output: 'a': 3, 'b': 1, 'n': 2
5. Find the First Non-Repeating Character
We need to find the first character that appears exactly once in the string.
Solution
public static char findFirstNonRepeatingChar(String str) {
if (str == null || str.isEmpty()) {
return '\0'; // Null character for invalid input
}
int[] frequency = new int[256];
// Count frequency
for (char c : str.toCharArray()) {
frequency[c]++;
}
// Find first character with frequency 1
for (char c : str.toCharArray()) {
if (frequency[c] == 1) {
return c;
}
}
return '\0'; // No non-repeating character
}
Explanation
- Use a frequency array to count occurrences of each character.
- Iterate through the string again to find the first character with a frequency of 1.
- Return a null character (
\0) if no such character exists. - Time Complexity: O(n).
- Space Complexity: O(1) due to fixed array size.
Example: Input: "swiss" → Output: 'w'
6. Remove Duplicate Characters
To remove duplicate characters, we can track seen characters and build a new string.
Solution
public static String removeDuplicates(String str) {
if (str == null || str.isEmpty()) {
return str;
}
boolean[] seen = new boolean[256];
StringBuilder result = new StringBuilder();
for (char c : str.toCharArray()) {
if (!seen[c]) {
seen[c] = true;
result.append(c);
}
}
return result.toString();
}
Explanation
- Use a boolean array to mark characters as seen.
- Build a new string with only the first occurrence of each character.
- Time Complexity: O(n).
- Space Complexity: O(1) for the boolean array, O(n) for the result string.
Example: Input: "hello" → Output: "helo"
7. Check if Two Strings are Anagrams
Two strings are anagrams if they contain the same characters with the same frequencies, ignoring order.
Solution
public static boolean areAnagrams(String str1, String str2) {
if (str1 == null || str2 == null || str1.length() != str2.length()) {
return false;
}
int[] frequency = new int[256];
// Count characters in str1 and decrement for str2
for (int i = 0; i < str1.length(); i++) {
frequency[str1.charAt(i)]++;
frequency[str2.charAt(i)]--;
}
// Check if all frequencies are zero
for (int count : frequency) {
if (count != 0) {
return false;
}
}
return true;
}
Explanation
- Check if lengths differ or inputs are null.
- Use a frequency array to increment counts for
str1and decrement forstr2. - If all counts are zero, the strings are anagrams.
- Time Complexity: O(n).
- Space Complexity: O(1).
Example: Input: "listen", "silent" → Output: true
8. Find All Permutations of a String
Finding all permutations involves generating all possible arrangements of the string’s characters using backtracking.
Solution
public static void printPermutations(String str) {
if (str == null || str.isEmpty()) {
return;
}
char[] charArray = str.toCharArray();
printPermutationsHelper(charArray, 0);
}
private static void printPermutationsHelper(char[] arr, int index) {
if (index == arr.length) {
System.out.println(new String(arr));
return;
}
for (int i = index; i < arr.length; i++) {
swap(arr, index, i);
printPermutationsHelper(arr, index + 1);
swap(arr, index, i); // Backtrack
}
}
private static void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Explanation
- Use backtracking to swap characters and generate permutations.
- Fix one character at a time and recursively permute the rest.
- Backtrack by swapping back to explore other permutations.
- Time Complexity: O(n!), where n is the string length.
- Space Complexity: O(n) for recursion stack.
Example: Input: "abc" → Output: abc, acb, bac, bca, cab, cba
9. Capitalize the First Letter of Each Word
We need to capitalize the first letter of each word in a sentence.
Solution
public static String capitalizeWords(String str) {
if (str == null || str.isEmpty()) {
return str;
}
char[] charArray = str.toCharArray();
boolean capitalizeNext = true;
for (int i = 0; i < charArray.length; i++) {
if (Character.isWhitespace(charArray[i])) {
capitalizeNext = true;
} else if (capitalizeNext && Character.isLetter(charArray[i])) {
charArray[i] = Character.toUpperCase(charArray[i]);
capitalizeNext = false;
} else {
charArray[i] = Character.toLowerCase(charArray[i]);
}
}
return new String(charArray);
}
Explanation
- Iterate through the string, tracking when to capitalize (after whitespace).
- Capitalize the first letter of each word and lowercase others.
- Time Complexity: O(n).
- Space Complexity: O(n) for the char array.
Example: Input: "hello world" → Output: "Hello World"
10. Count Words in a Sentence
To count words, we split the sentence by whitespace and count non-empty segments.
Solution
public static int countWords(String str) {
if (str == null || str.trim().isEmpty()) {
return 0;
}
int count = 0;
boolean inWord = false;
for (char c : str.toCharArray()) {
if (Character.isWhitespace(c)) {
inWord = false;
} else if (!inWord) {
inWord = true;
count++;
}
}
return count;
}
Explanation
- Track whether we’re inside a word using a boolean flag.
- Increment the word count when a non-whitespace character starts a new word.
- Handle null or empty strings.
- Time Complexity: O(n).
- Space Complexity: O(1).
Example: Input: "Hello world!" → Output: 2
Complete Code Example
Here’s the full Java class with all solutions for easy reference.
public class StringManipulation {
// 1. Reverse a String
public static String reverseString(String str) {
if (str == null || str.isEmpty()) {
return str;
}
char[] charArray = str.toCharArray();
int left = 0;
int right = charArray.length - 1;
while (left < right) {
char temp = charArray[left];
charArray[left] = charArray[right];
charArray[right] = temp;
left++;
right--;
}
return new String(charArray);
}
// 2. Check if a String is a Palindrome
public static boolean isPalindrome(String str) {
if (str == null || str.isEmpty()) {
return true;
}
str = str.toLowerCase();
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// 3. Count Vowels and Consonants
public static void countVowelsAndConsonants(String str) {
if (str == null || str.isEmpty()) {
System.out.println("Vowels: 0, Consonants: 0");
return;
}
str = str.toLowerCase();
int vowels = 0, consonants = 0;
Nursery Rhyme Generator
for (char c : str.toCharArray()) {
if (Character.isLetter(c)) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
vowels++;
} else {
consonants++;
}
}
}
System.out.println("Vowels: " + vowels + ", Consonants: " + consonants);
}
// 4. Count Frequency of Each Character
public static void countCharacterFrequency(String str) {
if (str == null || str.isEmpty()) {
System.out.println("Empty string");
return;
}
int[] frequency = new int[256];
for (char c : str.toCharArray()) {
frequency[c]++;
}
for (int i = 0; i < 256; i++) {
if (frequency[i] > 0) {
System.out.println("'" + (char)i + "': " + frequency[i]);
}
}
}
// 5. Find First Non-Repeating Character
public static char findFirstNonRepeatingChar(String str) {
if (str == null || str.isEmpty()) {
return '\0';
}
int[] frequency = new int[256];
for (char c : str.toCharArray()) {
frequency[c]++;
}
for (char c : str.toCharArray()) {
if (frequency[c] == 1) {
return c;
}
}
return '\0';
}
// 6. Remove Duplicate Characters
public static String removeDuplicates(String str) {
if (str == null || str.isEmpty()) {
return str;
}
boolean[] seen = new boolean[256];
StringBuilder result = new StringBuilder();
for (char c : str.toCharArray()) {
if (!seen[c]) {
seen[c] = true;
result.append(c);
}
}
return result.toString();
}
// 7. Check if Two Strings are Anagrams
public static boolean areAnagrams(String str1, String str2) {
if (str1 == null || str2 == null || str1.length() != str2.length()) {
return false;
}
int[] frequency = new int[256];
for (int i = 0; i < str1.length(); i++) {
frequency[str1.charAt(i)]++;
frequency[str2.charAt(i)]--;
}
for (int count : frequency) {
if (count != 0) {
return false;
}
}
return true;
}
// 8. Find All Permutations of a String
public static void printPermutations(String str) {
if (str == null || str.isEmpty()) {
return;
}
char[] charArray = str.toCharArray();
printPermutationsHelper(charArray, 0);
}
private static void printPermutationsHelper(char[] arr, int index) {
if (index == arr.length) {
System.out.println(new String(arr));
return;
}
for (int i = index; i < arr.length; i++) {
swap(arr, index, i);
printPermutationsHelper(arr, index + 1);
swap(arr, index, i);
}
}
private static void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 9. Capitalize First Letter of Each Word
public static String capitalizeWords(String str) {
if (str == null || str.isEmpty()) {
return str;
}
char[] charArray = str.toCharArray();
boolean capitalizeNext = true;
for (int i = 0; i < charArray.length; i++) {
if (Character.isWhitespace(charArray[i])) {
capitalizeNext = true;
} else if (capitalizeNext && Character.isLetter(charArray[i])) {
charArray[i] = Character.toUpperCase(charArray[i]);
capitalizeNext = false;
} else {
charArray[i] = Character.toLowerCase(charArray[i]);
}
}
return new String(charArray);
}
// 10. Count Words in a Sentence
public static int countWords(String str) {
if (str == null || str.trim().isEmpty()) {
return 0;
}
int count = 0;
boolean inWord = false;
for (char c : str.toCharArray()) {
if (Character.isWhitespace(c)) {
inWord = false;
} else if (!inWord) {
inWord = true;
count++;
}
}
return count;
}
// Main method for testing
public static void main(String[] args) {
System.out.println("1. Reverse: " + reverseString("hello"));
System.out.println("2. Is Palindrome: " + isPalindrome("Radar"));
System.out.print("3. Vowels and Consonants: ");
countVowelsAndConsonants("Hello World");
System.out.print("4. Character Frequency: ");
countCharacterFrequency("banana");
System.out.println("5. First Non-Repeating: " + findFirstNonRepeatingChar("swiss"));
System.out.println("6. Remove Duplicates: " + removeDuplicates("hello"));
System.out.println("7. Are Anagrams: " + areAnagrams("listen", "silent"));
System.out.println("8. Permutations of 'abc':");
printPermutations("abc");
System.out.println("9. Capitalize Words: " + capitalizeWords("hello world"));
System.out.println("10. Word Count: " + countWords("Hello world!"));
}
}
Conclusion
String manipulation is a fundamental skill for Java developers, and these ten problems cover a wide range of techniques, from basic iteration to advanced backtracking. By avoiding built-in functions where required and focusing on efficient algorithms, we’ve ensured that these solutions are both practical and educational. Whether you’re preparing for coding interviews or building robust applications, mastering these techniques will enhance your ability to handle strings effectively in Java.
Feel free to use the provided code, test it with different inputs, and adapt it to your needs. Happy coding!