Implementing String Algorithms

A website wants to know whether a new password contains a digit. A spelling game wants to count the vowels in a word. A puzzle app wants to know whether a phrase reads the same backward. In Topic 1.15 you could pull out one character with substring, but you had to know its index ahead of time, and a password could be 6 characters or 60. These questions need a program that looks at every character, however long the string is.

That is a job for a loop. The idea in plain words: start at the first position, look at the character there, move one position to the right, and repeat until you run out of characters. Going through a string one position at a time like this is called a traversal of the string.

Two facts from Topic 1.15 make this work:

• The indices of a string run from 0 to length() - 1.
• word.substring(i, i + 1) is the single character at index i, as a one-character String.

So a for loop from Topic 2.8 whose loop control variable i takes the values 0, 1, 2, …, length() - 1 can use i as the index.

for (int i = 0; i < word.length(); i++)
{
    String letter = word.substring(i, i + 1);
    // work with letter here
}

Take the header apart one piece at a time:

String word = "otter";
for (int i = 0; i < word.length(); i++)
{
    String letter = word.substring(i, i + 1);
    System.out.println(i + " " + letter);
}

index:      0 1 2 3 4
character:  o t t e r

0 o
1 t
2 t
3 e
4 r

Now change one thing: the update. With i += 2 instead of i++, the loop jumps two positions each time, so it visits only the characters at indices 0, 2, 4, and so on.

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

index:      0 1 2 3 4 5 6 7
character:  c o m p u t e r

i takes the values 0, 2, 4, and 6, so the loop prints c, m, u, and e, one per line. After 6 comes 8, and 8 < 8 is false. The condition i < word.length() still keeps every substring(i, i + 1) call safe, because i is never allowed to reach the length. The loop header decides which positions get visited; the body decides what happens at each one.

String word = "otter";
for (int i = 0; i <= word.length(); i++)
{
    System.out.println(word.substring(i, i + 1));
}

java.lang.StringIndexOutOfBoundsException: Range [5, 6) out of bounds for length 5

String word = "planet";
for (int i = 1; i < word.length(); i += 2)
{
    System.out.print(word.substring(i, i + 1));
}
System.out.println();

lnt

index:      0 1 2 3 4 5
character:  p l a n e t

Back to the password: does it contain at least one digit? Visiting every character is not enough by itself. The program also has to remember whether it has seen a digit yet, and it can only give an answer after the loop has looked at all of the characters.

Think of a lifeguard scanning a beach for a red umbrella. Before they start, the answer is “not seen yet.” The moment they spot one, they raise a flag. They might keep scanning, but the flag stays up, and at the end the flag tells you the answer. In code, that flag is a boolean variable. A flag is a boolean variable that starts with one value before a loop and is switched to the other value inside the loop when something you are watching for happens.

How does the program test whether a character is a digit? With a trick that uses indexOf from Topic 1.15. Put all the allowed characters in one string, "0123456789", and ask where the character appears in it. If the character is a digit, indexOf returns its position, a number 0 or more. If it is not a digit, indexOf returns -1.

String password = "tiger7x";
String digits = "0123456789";
boolean hasDigit = false;
for (int i = 0; i < password.length(); i++)
{
    String letter = password.substring(i, i + 1);
    if (digits.indexOf(letter) >= 0)
    {
        hasDigit = true;
    }
}
System.out.println("Has a digit: " + hasDigit);

index:      0 1 2 3 4 5 6
character:  t i g e r 7 x

Has a digit: true

Now flip the question: is every character a digit, as a PIN must be? The flag starts true (“no problem found yet”) and switches to false the moment a character fails. One bad character is enough to make the answer false, just as one digit was enough to make the first answer true.

String pin = "40x2";
String digits = "0123456789";
boolean allDigits = true;
for (int i = 0; i < pin.length(); i++)
{
    String letter = pin.substring(i, i + 1);
    if (digits.indexOf(letter) == -1)
    {
        allDigits = false;
    }
}
System.out.println("All digits: " + allDigits);

For "40x2", the characters 4 and 0 leave the flag alone. At x, indexOf returns -1, the condition == -1 is true, and allDigits becomes false. The 2 does not change it back. The output is All digits: false.

String password = "tiger7x";
String digits = "0123456789";
boolean hasDigit = false;
for (int i = 0; i < password.length(); i++)
{
    String letter = password.substring(i, i + 1);
    if (digits.indexOf(letter) >= 0)
    {
        hasDigit = true;
    }
    else
    {
        hasDigit = false;
    }
}
System.out.println("Has a digit: " + hasDigit);

String name = "ice cream";
boolean noSpaces = true;
for (int i = 0; i < name.length(); i++)
{
    if (name.substring(i, i + 1).equals(" "))
    {
        noSpaces = false;
    }
}
System.out.println(noSpaces);

Some properties are not about one character. Does a word contain a double letter, like the ll in balloon? Does a sentence contain the word cat somewhere? For a fixed piece of text like "cat", indexOf from Topic 1.15 can answer, but it cannot answer “are any two neighboring characters the same?”, because there is no single text to search for. A loop can.

The plan is the same traversal as before, but at each position i the program looks at more than one character: word.substring(i, i + 2) is the two characters starting at i, word.substring(i, i + 3) is three, and in general word.substring(i, i + n) is the n characters starting at index i.

That changes where the loop must stop. The end of each substring, i + n, may be at most word.length(). So the last starting index is word.length() - n.

index:      0 1 2 3 4 5 6
character:  b a l l o o n
two-character pieces start at 0 through 5:  ba al ll lo oo on

For "balloon", the length is 7, so the last two-character piece starts at 7 − 2 = 5. Either of these conditions stops the loop in the right place; they mean the same thing for whole numbers:

i <= word.length() - n
i < word.length() - n + 1

For two characters that is i <= word.length() - 2, which is the same as i < word.length() - 1.

String word = "balloon";
boolean hasDouble = false;
for (int i = 0; i < word.length() - 1; i++)
{
    String first = word.substring(i, i + 1);
    String second = word.substring(i + 1, i + 2);
    if (first.equals(second))
    {
        hasDouble = true;
        System.out.println("Double at index " + i);
    }
}
System.out.println("Has a double letter: " + hasDouble);

Double at index 2
Double at index 4
Has a double letter: true

Now vary the length. To look for "cat", every piece is three characters, so the loop stops at length() - 3:

String text = "concatenate";
for (int i = 0; i <= text.length() - 3; i++)
{
    String piece = text.substring(i, i + 3);
    if (piece.equals("cat"))
    {
        System.out.println("cat starts at index " + i);
    }
}

index:      0 1 2 3 4 5 6 7 8 9 10
character:  c o n c a t e n a t e

"concatenate" has length 11, so i goes from 0 to 8. The pieces are con, onc, nca, cat, ate, ten, ena, nat, ate. Only the piece starting at index 3 equals "cat", so the output is cat starts at index 3. The last piece, ate, starts at 8 and ends at index 10, the last character, so no piece is missed.

String word = "balloon";
for (int i = 0; i < word.length(); i++)
{
    System.out.println(word.substring(i, i + 2));
}

String word = "frog";
for (int i = 0; i < word.length() - 1; i++)
{
    System.out.println(word.substring(i, i + 2));
}

fr
ro
og

A flag answers “yes or no?”. Often the question is “how many?” How many vowels are in a word? How many times does "ana" appear in "banana"? In Topic 2.9 you counted how often a condition was met by using a counter: an int set to 0 before the loop and increased by 1 inside an if. Counting in a string is that same algorithm, with the traversal from this chapter supplying the values to test.

The difference from a flag is small but important. A flag stops changing once it is switched; a counter keeps going up every time the condition is true, so at the end it holds the total.

String word = "education";
String vowels = "aeiou";
int count = 0;
for (int i = 0; i < word.length(); i++)
{
    String letter = word.substring(i, i + 1);
    if (vowels.indexOf(letter) >= 0)
    {
        count++;
    }
}
System.out.println("Vowels: " + count);

index:      0 1 2 3 4 5 6 7 8
character:  e d u c a t i o n
count:      1 1 2 2 3 3 4 5 5

Vowels: 5

Now count a longer substring. The loop bound comes from 2.10.3: three-character pieces start at 0 through length() - 3.

String word = "banana";
int count = 0;
for (int i = 0; i <= word.length() - 3; i++)
{
    if (word.substring(i, i + 3).equals("ana"))
    {
        count++;
    }
}
System.out.println("ana appears " + count + " times");

index:      0 1 2 3 4 5
character:  b a n a n a

ana appears 2 times

Look at the two matches: one uses indices 1–3 and the other uses 3–5. They share the a at index 3. Because the loop checks every starting position, it counts overlapping matches: matches that share characters with each other. If you circled ana in banana with a pen and refused to reuse a letter, you would find only one. The loop finds two. When you trace a counting loop, check each starting index on its own; do not skip ahead past a match.

String word = "education";
for (int i = 0; i < word.length(); i++)
{
    int count = 0;
    if ("aeiou".indexOf(word.substring(i, i + 1)) >= 0)
    {
        count++;
    }
}
System.out.println("Vowels: " + count);

String word = "mississippi";
int count = 0;
for (int i = 0; i < word.length() - 1; i++)
{
    if (word.substring(i, i + 2).equals("ss"))
    {
        count++;
    }
}
System.out.println(count);

2

index:      0 1 2 3 4 5 6 7 8 9 10
character:  m i s s i s s i p p i

String word = "aaaa";
int count = 0;
for (int i = 0; i < word.length() - 1; i++)
{
    if (word.substring(i, i + 2).equals("aa"))
    {
        count++;
    }
}
System.out.println(count);

So far the algorithms have produced a boolean or an int. Sometimes the answer has to be a new string: a phrase with its spaces removed, a username made from parts of a name, a message with certain characters replaced. Strings are immutable (Topic 1.15), so the program cannot edit the original. Instead it builds a new string one piece at a time.

The pattern mirrors the counter. Before the loop, create a result variable holding the empty string, "", which has no characters. Inside the loop, add a piece to the end with += when you want it. After the loop, the result holds every piece that was added, in order. This is the same accumulator idea from Topic 2.9, where a variable collected a running total a little at a time; here it collects text instead of a number.

Each result += letter; concatenates and makes result refer to a new string object; the old one is not changed. The original string is never touched at all.

String phrase = "a big red dog";
String result = "";
for (int i = 0; i < phrase.length(); i++)
{
    String letter = phrase.substring(i, i + 1);
    if (!letter.equals(" "))
    {
        result += letter;
    }
}
System.out.println(result);
System.out.println(phrase);

abigreddog
a big red dog

Now vary what gets added. With an if/else, every pass adds something, but what it adds depends on the character. Here a space is replaced by an underscore and every other character is copied:

String phrase = "hop to it";
String result = "";
for (int i = 0; i < phrase.length(); i++)
{
    String letter = phrase.substring(i, i + 1);
    if (letter.equals(" "))
    {
        result += "_";
    }
    else
    {
        result += letter;
    }
}
System.out.println(result);

The output is hop_to_it. The result has the same length as the original, 9 characters, because exactly one piece is added on each pass. In the space-removing example, some passes added nothing, so the result was shorter.

String phrase = "a big red dog";
String result;
for (int i = 0; i < phrase.length(); i++)
{
    result += phrase.substring(i, i + 1);
}
System.out.println(result);

String word = "hop";
String result = "";
for (int i = 0; i < word.length(); i++)
{
    String letter = word.substring(i, i + 1);
    result += letter + letter;
}
System.out.println(result);

hhoopp

String word = "banana";
String result = "";
for (int i = 0; i < word.length(); i++)
{
    String letter = word.substring(i, i + 1);
    if ("aeiou".indexOf(letter) == -1)
    {
        result += letter;
    }
}
System.out.println(result);

Is "racecar" the same backward? What is "drawer" spelled backward? Both questions need a new string with the characters in the opposite order. That is a special case of building a new string from 2.10.5: the pieces are the same characters, and only the order changes. There are two ways to get that order.

Way 1: go forward, but add each character to the front. The concatenation letter + reversed puts the new character before everything collected so far. Each new character pushes the earlier ones to the right, so the first character ends up last.

String word = "stop";
String reversed = "";
for (int i = 0; i < word.length(); i++)
{
    String letter = word.substring(i, i + 1);
    reversed = letter + reversed;
}
System.out.println(reversed);

pots

Way 2: go backward, and add each character to the end. Change the loop instead of the concatenation. Start at the last index, word.length() - 1, keep going while i >= 0, and subtract 1 each time. Then the ordinary += adds the characters in reverse order.

String word = "drawer";
String reversed = "";
for (int i = word.length() - 1; i >= 0; i--)
{
    reversed += word.substring(i, i + 1);
}
System.out.println(reversed);

index:      0 1 2 3 4 5
character:  d r a w e r

i takes the values 5, 4, 3, 2, 1, 0, which add r, e, w, a, r, d. The output is reward. The condition i >= 0 includes index 0, so the first character is added last; after that i becomes -1 and the loop ends.

Both ways give a correct reverse. Use whichever reads more clearly to you, but be ready to trace either one.

String word = "drawer";
String reversed = "";
for (int i = word.length(); i >= 0; i--)
{
    reversed += word.substring(i, i + 1);
}
System.out.println(reversed);

String word = "stop";
String reversed = "";
for (int i = 0; i < word.length(); i++)
{
    String letter = word.substring(i, i + 1);
    reversed = reversed + letter;
}
System.out.println(reversed);

stop

A palindrome is text that reads the same forward and backward, such as level or racecar. The phrase never odd or even is a palindrome too, if you ignore the spaces. Checking it uses two algorithms from this chapter, one after the other, and then a comparison from Topic 1.15.

String phrase = "never odd or even";
String letters = "";
for (int i = 0; i < phrase.length(); i++)
{
    String letter = phrase.substring(i, i + 1);
    if (!letter.equals(" "))
    {
        letters += letter;
    }
}
String reversed = "";
for (int i = letters.length() - 1; i >= 0; i--)
{
    reversed += letters.substring(i, i + 1);
}
System.out.println(letters);
System.out.println(reversed);
System.out.println("Palindrome: " + letters.equals(reversed));

Step 1, lines 2–10: build a new string without spaces (2.10.5). letters starts as "", and every character that is not a space is added to the end. After the loop, letters holds neveroddoreven, 14 characters.

Step 2, lines 11–15: reverse it (2.10.6). The second loop starts at index 13, the last index of letters (not of phrase), and moves down to 0, adding each character to the end of reversed.

index:      0 1 2 3 4 5 6 7 8 9 10 11 12 13
letters:    n e v e r o d d o r e  v  e  n

Reading the row from index 13 down to 0 gives n e v e r o d d o r e v e n, the same characters in the same order, so reversed is also neveroddoreven.

Step 3, line 18: compare. letters.equals(reversed) checks whether the two strings hold the same characters, and it is true.

neveroddoreven
neveroddoreven
Palindrome: true

Notice that the second loop uses letters.length(), not phrase.length(). The phrase has 17 characters, so a second loop written as for (int i = phrase.length() - 1; i >= 0; i--) would start at index 16 of letters, which has only 14 characters, and the program would crash with a StringIndexOutOfBoundsException before printing anything. Whenever one algorithm feeds another, each loop must be bounded by the string it actually reads.

• A traversal visits every character: loop i from 0 while i < s.length() and use s.substring(i, i + 1). The last index is length() - 1, and going one past it throws a StringIndexOutOfBoundsException.
• To look at substrings of length n, use s.substring(i, i + n) and stop at i <= s.length() - n.
• A flag answers a yes-or-no question about a string: start false and switch to true to ask “does any character…?”, or start true and switch to false to ask “does every character…?”. Never switch it back inside the loop.
• A counter answers “how many?”: start at 0 before the loop and add 1 for each match. Checking every starting index counts overlapping matches.
• To build a new string, start at "" and add pieces with +=. To reverse, either add each character to the front while looping forward, or loop from the last index down to 0 and add to the end.

String code = "abcdefg";
String result = "";
for (int i = 0; i < code.length(); i += 2)
{
    result = code.substring(i, i + 1) + result;
}
System.out.println(result);

geca

String text = "bathe the";
int count = 0;
for (int i = 0; i < text.length() - 3; i++)
{
    if (text.substring(i, i + 3).equals("the"))
    {
        count++;
    }
}
System.out.println(count);

for (int i = 0; i <= text.length() - 3; i++)

// I
for (int i = 0; i < word.length(); i++)
{
    reversed = word.substring(i, i + 1) + reversed;
}

// II
for (int i = word.length() - 1; i >= 0; i--)
{
    reversed += word.substring(i, i + 1);
}

// III
for (int i = word.length() - 1; i > 0; i--)
{
    reversed += word.substring(i, i + 1);
}

String word = "rhythmic";
int i = 0;
boolean found = false;
while (i < word.length() && !found)
{
    if ("aeiou".indexOf(word.substring(i, i + 1)) >= 0)
    {
        found = true;
    }
    else
    {
        i++;
    }
}
System.out.println(found + " " + i);

true 6

index:      0 1 2 3 4 5 6 7
character:  r h y t h m i c

String sentence = "go  home now";
int spaces = 0;
for (int i = 0; i < sentence.length(); i++)
{
    if (sentence.substring(i, i + 1).equals(" "))
    {
        spaces++;
    }
}
System.out.println("Words: " + (spaces + 1));

String word = "level";
String reversed = "";
for (int i = word.length() - 1; i >= 0; i--)
{
    reversed += word.substring(i, i + 1);
}
System.out.println(reversed);
System.out.println(reversed == word);

System.out.println(reversed.equals(word));

Check each statement. If the answer is “not yet,” reread the linked subsection.

• I can write the loop header that visits every character of a string and explain why it uses less than, not less than or equal. Reread
• I can use a flag to check whether any character, or every character, has a property. Reread
• I can choose the loop bound that reaches every substring of a given length. Reread
• I can count the characters or substrings that meet a condition, including overlapping matches. Reread
• I can trace an algorithm that builds a new string with +=. Reread
• I can reverse a string in two ways and spot a loop that only copies it. Reread