Implementing String Algorithms

Hello there! I'm Saavi, and I'm excited to dive into one of my favorite topics: string algorithms. It sounds complicated, but I promise it's just about giving the computer smart instructions for handling text.

Think of a String in Java as a train. Each car on the train holds exactly one character. The string "Boston" is a train with 6 cars: B, o, s, t, o, n. An algorithm is our plan for inspecting this train. Most of our plans will involve a for loop, which is like walking from the engine to the caboose, one car at a time.

The Basic Toolkit

To work with strings, we need a few key methods you've already seen:

• str.length(): Tells you how many characters (cars) are in the string (train).
• str.charAt(i): Gets the character at a specific index i.
• str.substring(i, j): Gets a new string that's a piece of the original, from index i up to (but not including) index j.
• + (Concatenation): Lets you join strings together to build a new one.

With just these tools and a for loop, you can accomplish almost anything.

Standard Algorithm 1: Finding if Substrings Have a Property

Let's say we want to know if a password contains at least one number. The "property" we're looking for is "is a digit." We can write an algorithm for this.

The plan:

1. Go through the string, character by character.
2. At each character, ask: "Is this a digit?"
3. If you find one, you're done! The answer is true. You can stop looking.
4. If you get to the end of the string and haven't found any digits, the answer is false.

Here’s how that looks in code:

public boolean hasNumber(String str) {
  // Loop through each character of the string
  for (int i = 0; i < str.length(); i++) {
    // Get the character at the current index
    char current = str.charAt(i);

    // Check if it has the property (is a digit)
    if (Character.isDigit(current)) {
      return true; // Found one! We can stop and return immediately.
    }
  }

  // If the loop finishes without finding a digit, we know there are none.
  return false;
}

This pattern—looping through, checking a condition, and returning true early—is incredibly common and efficient.

Standard Algorithm 2: Counting Substrings with Criteria

Now, let's level up. Instead of just finding if something exists, let's count how many times it appears. Let's try to count how many times the substring "an" appears in the word "banana".

Our eyes can see it: banana -> an is at index 1. banana -> an is at index 3. The answer is 2. How do we teach a computer to do this?

The plan:

1. Create a counter variable, initialized to 0.
2. Loop through the string, but not all the way to the end. We need to grab two characters at a time ("an" is length 2), so we must stop early enough to not go out of bounds.
3. In each iteration, grab a substring of length 2.
4. Check if that substring .equals("an").
5. If it does, increment your counter.
6. After the loop finishes, return the counter.

public int countAn(String str) {
  int count = 0;
  // The loop must stop so that the substring call is valid.
  // str.substring(i, i + 2) needs i + 2 to be <= str.length().
  // So, i must be < str.length() - 1.
  for (int i = 0; i < str.length() - 1; i++) {
    String twoChars = str.substring(i, i + 2);
    if (twoChars.equals("an")) {
      count++;
    }
  }
  return count;
}

Standard Algorithm 3: Creating a Reversed String

This is a classic problem you'll definitely see. How do you take a string like "Priya" and turn it into "ayirP"?

You can't change the original string (remember, strings are immutable!). You have to build a new one.

The plan:

1. Create an empty string to hold our result, like String reversed = "";.
2. Loop through the original string, but start at the end and go backwards.
3. In each step of the loop, grab the character at the current index.
4. Add that character to the end of your reversed string.
5. After the loop is done, reversed will hold the complete, reversed string.

public String reverseString(String str) {
  String result = "";
  // Start at the last character's index: length() - 1
  // Keep going as long as i is 0 or more
  // Decrement i each time
  for (int i = str.length() - 1; i >= 0; i--) {
    char c = str.charAt(i);
    result = result + c; // Or result += c;
  }
  return result;
}

Look closely at that for loop. It’s a bit different. We start i at the last valid index (str.length() - 1), we continue as long as i is greater than or equal to 0, and we decrement i with i--. This backward loop is a fundamental technique you should get comfortable with.

These three patterns form the foundation for almost any string problem you'll face on the AP exam. Master them, and you'll be in great shape.

Let's walk through a few problems together. The key is not just to get the right answer, but to understand the process.

public int countVowels(String str) {
  int vowelCount = 0;
  String lowerStr = str.toLowerCase();
  for (int i = 0; i < lowerStr.length(); i++) {
    char c = lowerStr.charAt(i);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
      vowelCount++;
    }
  }
  return vowelCount;
}

public String removeChar(String str, char ch) {
  String result = "";
  for (int i = 0; i < str.length(); i++) {
    char current = str.charAt(i);
    if (current != ch) {
      result += current;
    }
  }
  return result;
}

Ready to try a couple on your own? Think through the plan first, then write the code.

Problem 1: Palindrome Checker

A palindrome is a word that reads the same forwards and backwards, like "racecar" or "level". Write a method isPalindrome(String str) that returns true if the given string is a palindrome and false otherwise. The check should be case-insensitive.

• Hint 1
  How can you use one of the algorithms we already discussed today to help you?
• Hint 2
  Once you have a reversed version of the string, what method should you use to compare it to the original? Don't forget to handle uppercase and lowercase letters!

Problem 2: Every Other Letter

Write a method everyOther(String str) that returns a new string made of every other letter starting with the first. For example, calling everyOther("Chicago") should return "Chcao".

• Hint 1
  You'll need a for loop, but how should you change the increment step (i++) to skip characters?
• Hint 2
  You'll be building a new string, so start with an empty String result = "";.