2.10 Implementing String Algorithms

What you need to know

• Iterate over characters with for (int i = 0; i < s.length(); i++) and get each one as a String: s.substring(i, i + 1).
• Named algorithms: count occurrences of a substring; find all positions of a substring; reverse a String; check for a palindrome; build a new String from selected characters.
• Counting substrings: loop i from 0 to s.length() - sub.length() (inclusive) and check s.substring(i, i + sub.length()).equals(sub). The upper bound prevents an out-of-bounds substring call.
• Reverse: start with an empty String and prepend each character: rev = s.substring(i, i + 1) + rev;
• Building a String: start with "" and concatenate. Strings are immutable, so you're creating a new one each time — fine at exam scale.
• indexOf finds the first occurrence only. To find all, loop or use substring to search the remainder.

Worked example

// count occurrences of sub in s (overlapping allowed)
public static int countOf(String s, String sub)
{
    int count = 0;
    for (int i = 0; i <= s.length() - sub.length(); i++)
    {
        if (s.substring(i, i + sub.length()).equals(sub))
        {
            count++;
        }
    }
    return count;
}
// countOf("banana", "ana") → 2 (indices 1 and 3)

// reverse
String rev = "";
for (int i = 0; i < s.length(); i++)
{
    rev = s.substring(i, i + 1) + rev;
}

Trace it yourself

Step through with the buttons, or use the ← → keys. Changed variables are highlighted.

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• The CED's named String algorithms: find whether a String contains a substring; count occurrences of a substring; find all positions of a substring; reverse a String; determine if a String is a palindrome; create a new String from selected characters of another.
• Character-by-character loop: for (int i = 0; i < s.length(); i++) with String c = s.substring(i, i + 1);. Since there's no charAt on the reference sheet, every character is a one-length String. Compare with .equals.
• Substring-window loop: to check every substring of length k, loop i from 0 to s.length() - k inclusive and examine s.substring(i, i + k). The bound is the single most-tested detail: too high throws an exception; too low misses the last window.
• Reverse: prepend each character to an accumulator: rev = s.substring(i, i + 1) + rev;. Or loop from the end appending. Both work.
• Palindrome: compare s with its reverse using .equals, or compare characters from both ends moving inward with a loop to the middle.
• Find all occurrences: loop the window and record each i where the window equals the target. Overlapping matches ("aa" in "aaa" at 0 and 1) are found by this method; indexOf alone only finds the first.
• Building a filtered String: start with "", loop characters, append those that pass the test. Remove vowels, keep digits, etc.

Mistakes that cost points

• Off-by-one on the window bound. i <= s.length() - k. Not <, not - k + 1.
• Using == to compare the window. Always .equals.
• Appending instead of prepending for reverse. rev += c copies; rev = c + rev reverses.
• Forgetting Strings are immutable. Every operation needs its result stored.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.

String s = "abcde";
String r = "";
for (int i = 0; i < s.length(); i += 2)
{
    r = s.substring(i, i + 1) + r;
}
System.out.println(r);

for (int i = 0; /* condition */ ; i++)
{
    if (s.substring(i, i + 2).equals("ab")) return true;
}
return false;