# String Manipulation Algorithms

Notes on string manipulation algorithms from various sources:

## Counting vowels in a string

``````public int countVowels(String str) {
int count = 0;
String vowels = "aeiou"; // or a set!
for (var ch : str.toCharArray())
if (vowels.contains(Character.toString(ch)))
count++;
return count;
}``````

An alternative to `vowels.contains(Character.toString(ch))` is `vowels.indexOf(ch) != -1`.

## Reversing a string

Two possible solutions, loop and add to stack and then pop out into string, or loop from the end and add to string.

``````public String reverse(String str) {
String reversed = "";
for (var i = str.length() - 1; i >= 0; i--)
reversed += str.charAt(i);
return reversed;
}``````

At `reversed += str.charAt(i);`, every time we append a new character to the string `reversed`, we are creating a new string object and all the characters are being copied to the new string, so `O(n)`. Also, the loop itself is `O(n)`. This means this soluction is quadratic, not good. Instead, prefer `StringBuilder` for creating mutable strings, to append each new character that we read without the overhead of re-creating another string object in memory. The `StringBuilder` is `O(1)` and the loop is `O(n)`!

``````public String reverse(String str) {
StringBuilder reversed = new StringBuilder();
for (var i = str.length() - 1; i >= 0; i--)
reversed.append(str.charAt(i));
return reversed.toString();
}``````

## Reversing a sentence

Task: `"Trees are beautiful"``"beautiful are Trees"`

``````    public String reverse(String sentence) {
String[] words = sentence.split(" ");
StringBuilder reversed = new StringBuilder();
for (var i = words.length -1; i >= 0; i--)
reversed.append(words[i] + " ");
return reversed.toString().trim();
}``````

Or using Java utility classes:

``````public String reverse(String sentence) {
String[] words = sentence.split(" ");

// convert String[] into ArrayList and reverse it
Collections.reverse(Arrays.asList(words));

return String.join(" ", words).trim();
}``````

## Checking if two strings are rotations of each other

``````public boolean areRotations(String str1, String str2) {
if (str1.length() != str2.length())
return false;

if (!(str1 + str1).contains(str2))
return false;

return true;
}``````

## Removing duplicates from a string

``````public String removeDuplicates(String str) {
StringBuilder output = new StringBuilder();
Set<Character> seen = new HashSet<>();
for (var ch : str.toCharArray()) {
if (!seen.contains(ch))
}
return output.toString();
}``````

## Finding the most repeated character in a string

``````public char getMaxOccuringChar(String str) {

// populate frequencies hash table
Map<Character, Integer> frequencies = new HasMap<>();
for (var ch : str.toCharArray()) {
if (frequencies.containsKey(ch))
frequencies.replace(ch, frequencies.get(ch) + 1);
else
frequencies.put(ch, 1);
}

// iterate over frequencies hash table and pick out highest number
int max = 0;
char result = "";
for (var key : frequencies.keySet()
char charValue = frequencies.get(key);
if (charValue > max)
max = charValue;
result = key;
return result;
}``````

## Capitalizing the first letter of every word in a sentence

``````public String capitalize(String sentence) {
String[] words = sentence.trim().split(" ");
for (i = 0; i < words.length; i++)
words[i] = words[i].substring(0, 1).toUpperCase()
+ words[i].substring(1).toLowerCase;
return String.join(" ", words);
}``````

## Checking if two strings are anagrams of each other

``````public boolean areAnagrams(String str1, String str2) {
var array1 = str1.toCharArray();
var array2 = str2.toCharArray();
Arrays.sort(array1);
Arrays.sort(array2);
Arrays.equals(array1, array2);
}``````

## Checking if a string is a palindrome

``````public boolean isPalindrome(String word) {
var input = new StringBuilder(word);
input.reverse();
return input.toString().equals(word);
}``````

Alternative approach using two pointers, one at the first index and one at the last index, comparing them and moving them inward to compare again:

``````public boolean isPalindrome(String word) {
int left = 0
int right = word.length() - 1;

while (left < right) {
if (word.charAt(left++) != word.charAt(right--))
return false;

return true;
}

var input = new StringBuilder(word);
input.reverse();
return input.toString().equals(word);
}``````