String Algorithms: A Last-Minute Review 🚀

Welcome! This guide is designed to be your ultimate resource for string algorithms right before the exam. Let's get you feeling confident and ready to ace those questions!

String Algorithms Overview

Key String Methods

• length(): Returns the length of the string.
• substring(int beginIndex, int endIndex): Returns a substring starting at beginIndex (inclusive) and ending at endIndex (exclusive).
• equals(String other): Checks if two strings have the same sequence of characters.

Reversing a String

String reversal is a classic algorithm that demonstrates how to build a new string by prepending characters from the original string.

Algorithm:

1. Initialize an empty string called result.
2. Iterate through the input string s from the beginning to the end.
3. In each iteration, take the current character and add it to the beginning of result.
4. Return result.

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

Example:

If s is "hello", the algorithm works like this:

• i = 0: result becomes "h"
• i = 1: result becomes "eh"
• i = 2: result becomes "leh"
• i = 3: result becomes "lleh"
• i = 4: result becomes "olleh"

Getting All Substrings of Length N

This algorithm uses a "sliding window" approach to extract all substrings of a given length. It's a fundamental technique for many string problems.

Algorithm:

1. Iterate through the input string s using a loop.
2. The loop condition ensures that the substring of length n does not go out of bounds.
3. In each iteration, extract a substring of length n starting at the current index i.
4. Print or process the substring.

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));
    }
}

Analogy: Imagine a window of width n sliding across the string. The loop moves the window one character at a time.

Example:

If s is "abcdef" and n is 3, the substrings are:

• "abc"
• "bcd"
• "cde"
• "def"

Checking for a Substring

This algorithm checks if a given substring exists within a larger string. It's a common task in text processing.

Algorithm:

1. Iterate through the input string s using a loop.
2. In each iteration, extract a substring of the same length as the target substring n.
3. Compare the extracted substring with n using the equals() method.
4. If a match is found, return true immediately.
5. If the loop finishes without finding a match, 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;
}

Example:

`checkForSubstring("programming