About Implementing Suffix Arrays (with.Java)

Implementing a suffixed array (with.Java).

We’re going to learn by solving a coding test problem, reflecting on the problem we solved, and exploring other ways to solve it. Let’s start with the problem.

Problem

For some strings, a suffix means a string starting at a certain index. For example, all suffixes for “banana” are “banana”, “anana”, “nana”, “ana”, “na”, and “a”. Given a string my_string as a parameter, write a solution function that returns an array of strings sorted alphabetically by all suffixes in my_string.

Example input and output

my_string: “banana” result: [“a”, “ana”, “anana”, “banana”, “na”, “nana”]

In other words, my_string is “banana” and all suffixes are like the description in the question. Sorting it alphabetically would return [“a”, “ana”, “anana”, “banana”, “na”, “nana”] because it is “a”, “ana”, “anana”, “banana”, “na”, “nana”.

My solution to the problem

import java.util.*;
class Solution {
    public String[] solution(String my_string) {
        ArrayList<String> arr = new ArrayList<String>();
        for(int i = 0; i < my_string.length(); i++){
            arr.add(my_string.substring(i));
        }
        Collections.sort(arr);
        String[] answer = new String[arr.size()];
        for(int j = 0; j < arr.size(); j++){
            answer[j] = arr.get(j);
        }
        } return answer;
    }
}

Explanation of the solution

The way to store all the suffixes in an array is to strip them off one character at a time and store them in an array. To do this, we used substring() to insert a loop into an ArrayList, iterating over the length of the string to be suffixed with my_string.length(). This actually separated all the suffixes, but for the required result, I wanted them to be sorted in pre-edited order, so I used Collections’ sort() to sort the elements in the array.