← Home

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))
            seen.add(ch);
            output.add(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);
}