4.3 Developing Algorithms Using Strings

Using for loops, we can also develop many useful algorithms with Strings. There are several that you need to know in this course. The focus of this topic is on developing algorithms using Strings. (For more information about the String methods that you should know for the exam, you can visit this guide!)

If you ever have issues understanding or writing an algorithm that works with Strings, it helps to use a short String (like "house") to test what the algorithm actually does. You can use scratch paper to trace the indices and see every step of the algorithm. 

Reversing a String

To reverse a string, we need to go get the first character and make it into a String. Then we get the 2nd character and put it before the first character. Then we repeat until all the characters are used up.

public static String reverse(String s) {
  String result = ""
  for (int i = 0; i < string.length(); i++) {
    result = s.substring(i,i+1) + result;
  }
  return result;
}

Get All Substrings of Length N

This can be used to print all characters in the string by setting the length n to 1. To get longer substrings, we increase n to the length of the substrings you want to find. This value can be up to the length of the overall string itself, but no more. This would create an exception. 

How this algorithm works is similar to a sliding window. The beginning of the window is at the beginning of the substring you want to print and the end of the window is the end of the substring. Therefore the width of the rectangle is n. 

We first set the window to start at the beginning of the string. This corresponds to the loop initialization. Then, the window slides to the right by one character every iteration to represent the loop increment. The loop stops when the end of the window reaches the end of the string. 

To achieve this, we need the beginning of the window to be less than the length of the string + 1 - n.

public static void printSubstringsLengthN(String s, int n) {
  for (int i = 0; i < (s.length() + 1 - n); i++) {
    System.out.println(s.substring(i, i+n));
  }
}

Check for a Substring

We can easily adapt the method above to check if there are any substrings in an input String that consist of a desired sequence of characters. 

Calling the method below with checkForSubstring("house", "us"); would return true while checkForSubstring("bob", "us"); would return false. 

public static boolean checkForSubstring(String s, String n) {
  for (int i = 0; i < (s.length() + 1 - n.length()); i++) {
    String currentSubString = (s.substring(i, i+n.length()));
    if (currentSubString.equals(n)) {
        return true;
    }
  }
  return false;
}

Count Substrings Satisfying a Criteria

We can also adapt the methods we have used so far to count the number of substrings in an input String that meet a certain criteria. 

Calling the method below with countSubstrings("banana", "a"); will return the number of times the letter "a" is in the word "banana," which is 3 in this case. We can also call countSubstrings("ABBBAABBAABBABAB", "ABBA"); which will return the number of times "ABBA" is in the input String, which in this case is 2.

public static int countSubstrings(String s, String n) {
  int count = 0;
  for (int i = 0; i < (s.length() + 1 - n.length()); i++) {
    String currentSubString = (s.substring(i, i+n.length()));
    if (currentSubString.equals(n)) {
        count++;
    }
  }
  return count;
}