How to Count Number of Distinct Substrings in a String -

laptop infographic online business 6087062

Introduction

Counting the number of distinct substrings in a string is a classic problem in computer science and string processing. A substring is a sequence of characters that appear consecutively within a string. For instance, the string “abc” contains substrings such as “a”, “ab”, “abc”, “b”, “bc”, and “c”. The objective is to determine the total number of distinct substrings that can be generated from a given input string.

Problem Explanation

Given a string s, determine how many distinct substrings it contains, including the empty substring (often excluded depending on the definition). The challenge lies in efficiently computing this number without redundantly generating all possible substrings.

Naive Approach and Its Limitations

A brute-force method would involve generating all substrings and storing them in a hash set to filter duplicates. While this works for small strings, it is highly inefficient with a time complexity of O(n³) in the worst case, due to substring generation and set operations.

Efficient Approach Using Suffix Trie or Suffix Automaton

A more optimal approach involves using advanced data structures like a suffix trie, suffix tree, or suffix automaton. However, these can be complex to implement. An alternative, efficient, and relatively simpler method uses the Suffix Array and Longest Common Prefix (LCP) array to count distinct substrings in O(n log n) time.

Java Implementation Using Suffix Array and LCP

Here’s an efficient Java implementation that counts the number of distinct substrings using the suffix array and LCP array:

public class DistinctSubstrings {

    public static int countDistinctSubstrings(String inpustString) {
        inpustString += "$"; // Append terminal character
        int k = inpustString.length();
        int[] suffixArr = buildSuffixArr(inpustString);
        int[] lcp = buildLCPArray(inpustString, suffixArr);

        int total = 0;
        for (int i = 1; i < k; i++) {
            int suffixLength = k - 1 - suffixArr[i]; // Exclude terminal character
            total += suffixLength - lcp[i - 1];
        }
        return total;
    }

    private static int[] buildSuffixArr(String inputString) {
        int n = inputString.length();
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;

        int[] rankArr = new int[n];
        for (int i = 0; i < n; i++) rankArr[i] = inputString.charAt(i);

        int[] temp = new int[n];
        for (int len = 1; len < n; len *= 2) {
            final int l = len;
            Arrays.sort(order, (a, b) -> {
                if (rankArr[a] != rankArr[b]) return Integer.compare(rankArr[a], rankArr[b]);
                int ra = (a + l < n) ? rankArr[a + l] : -1;
                int rb = (b + l < n) ? rankArr[b + l] : -1;
                return Integer.compare(ra, rb);
            });

            temp[order[0]] = 0;
            for (int i = 1; i < n; i++) {
                temp[order[i]] = temp[order[i - 1]];
                if (rankArr[order[i]] != rankArr[order[i - 1]] ||
                    ((order[i] + l < n ? rankArr[order[i] + l] : -1) != 
                     (order[i - 1] + l < n ? rankArr[order[i - 1] + l] : -1))) {
                    temp[order[i]]++;
                }
            }
            System.arraycopy(temp, 0, rankArr, 0, n);
        }

        int[] sa = new int[n];
        for (int i = 0; i < n; i++) sa[i] = order[i];
        return sa;
    }

    private static int[] buildLCPArray(String inputString, int[] sa) {
        int n = inputString.length();
        int[] rankArr = new int[n];
        for (int i = 0; i < n; i++) rankArr[sa[i]] = i;

        int[] lcp = new int[n - 1];
        int h = 0;
        for (int i = 0; i < n; i++) {
            if (rankArr[i] > 0) {
                int j = sa[rankArr[i] - 1];
                while (i + h < n && j + h < n && inputString.charAt(i + h) == inputString.charAt(j + h)) {
                    h++;
                }
                lcp[rankArr[i] - 1] = h;
                if (h > 0) h--;
            }
        }
        return lcp;
    }

    public static void main(String[] args) {
        String input = "banana";
        int result = countDistinctSubstrings(input);
        System.out.println("Number of distinct substrings: " + result);
    }
}

Example Walkthrough

For the input “banana”, there are 15 unique substrings. These include: “a”, “an”, “ana”, “anan”, “anana”, “b”, “ba”, “ban”, “bana”, “banan”, “banana”, “n”, “na”, “nan”, and “nana”.
It’s important to note that the empty string is excluded from this count.

Conclusion

Counting distinct substrings can be computationally expensive with a naive approach, but leveraging the suffix array and LCP array offers an efficient and scalable solution. The Java code provided illustrates a practical implementation suitable for intermediate to advanced programmers familiar with string algorithms.

You can find the example code on Github.