Fiveable
Fiveable

or

Log in

Find what you need to study


Light

Find what you need to study

4.3 Developing Algorithms Using Strings

3 min readdecember 23, 2022

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

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 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 

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 . 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 . Then, the window slides to the right by one character every iteration to represent the . 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;
}

Key Terms to Review (6)

Equals Method

: The equals method is a method in Java that is used to compare two objects for equality. It checks if the values of the objects are the same, rather than comparing their memory addresses.

For Loop

: A for loop is a control flow statement that allows you to repeatedly execute a block of code for a specified number of times or until certain conditions are met.

Loop Increment

: Loop increment is the step in programming where variables are updated or modified after each iteration of a loop. It determines how the loop progresses and when it will eventually terminate.

Loop Initialization

: Loop initialization is the step in programming where variables are assigned initial values before entering a loop. It sets up the starting conditions for the loop's execution.

Reverse

: Reversing a string means to change the order of its characters, so that the last character becomes the first, the second-to-last becomes the second, and so on.

Sliding Window

: A sliding window is a technique used in computer science and algorithms where a fixed-size window moves through an array or string to perform operations on subarrays or substrings. It allows for efficient processing of data by avoiding redundant calculations.

4.3 Developing Algorithms Using Strings

3 min readdecember 23, 2022

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

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 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 

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 . 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 . Then, the window slides to the right by one character every iteration to represent the . 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;
}

Key Terms to Review (6)

Equals Method

: The equals method is a method in Java that is used to compare two objects for equality. It checks if the values of the objects are the same, rather than comparing their memory addresses.

For Loop

: A for loop is a control flow statement that allows you to repeatedly execute a block of code for a specified number of times or until certain conditions are met.

Loop Increment

: Loop increment is the step in programming where variables are updated or modified after each iteration of a loop. It determines how the loop progresses and when it will eventually terminate.

Loop Initialization

: Loop initialization is the step in programming where variables are assigned initial values before entering a loop. It sets up the starting conditions for the loop's execution.

Reverse

: Reversing a string means to change the order of its characters, so that the last character becomes the first, the second-to-last becomes the second, and so on.

Sliding Window

: A sliding window is a technique used in computer science and algorithms where a fixed-size window moves through an array or string to perform operations on subarrays or substrings. It allows for efficient processing of data by avoiding redundant calculations.


© 2024 Fiveable Inc. All rights reserved.

AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.


© 2024 Fiveable Inc. All rights reserved.

AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.