Question

Formatted question description: https://leetcode.ca/all/1698.html

 1698. Number of Distinct Substrings in a String

 Given a string s, return the number of distinct substrings of s.

 A substring of a string is obtained by deleting any number of characters (possibly zero)
 from the front of the string and any number (possibly zero) from the back of the string.


 Example 1:

 Input: s = "aabbaba"
 Output: 21
 Explanation: The set of distinct strings is ["a","b","aa","bb","ab","ba","aab","abb","bba","aba","aabb","abba","bbab","baba","aabba","abbab","bbaba","aabbab","abbaba","aabbaba"]

 Example 2:

 Input: s = "abcdefg"
 Output: 28


 Constraints:
     1 <= s.length <= 500
     s consists of lowercase English letters.


 Follow up: Can you solve this problem in O(n) time complexity?

Algorithm

Use a Trie, and every time a new Trie node created, meaning a new substring.

If O(n) time complexity, then we need some extra space to store for de-dup check, like a Set.

Code

Java

public class Number_of_Distinct_Substrings_in_a_String {

    class Solution_oN {

        int result = 0;
        Node trie[] = new Node[26];

        class Node {
            Node children[] = new Node[26];
            int count = 0;
        }

        public int countDistinct(String s) {
            for (int i = 0; i < s.length(); i++) {
                insert(trie, s, i);
            }

            for (int i = 0; i < s.length(); i++) {
                find(trie, s, i);
            }

            return result;
        }

        public void insert(Node trie[], String s, int index) {
            if (index >= s.length()) {
                return;
            }

            int i = s.charAt(index) - 'a';
            if (trie[i] == null) {
                trie[i] = new Node();
            }

            insert(trie[i].children, s, index + 1);
        }

        public void find(Node trie[], String s, int index) {
            if (index >= s.length()) {
                return;
            }

            int i = s.charAt(index) - 'a';
            trie[i].count++;

            if (trie[i].count == 1) {
                this.result++;
            }

            find(trie[i].children, s, index + 1);
        }

    }

    public class Solution {
        class Trie {
            Trie[] children = new Trie[26];
        }

        public int countDistinct(String s) {
            Trie root = new Trie();
            Trie current;
            int count = 0;
            for (int i = 0; i < s.length(); i++) {
                current = root;
                for (int j = i; j < s.length(); j++) {

                    if (current.children[s.charAt(j) - 'a'] == null) {
                        current.children[s.charAt(j) - 'a'] = new Trie();
                        count++;
                    }

                    current = current.children[s.charAt(j) - 'a'];
                }
            }

            return count;
        }
    }

    public class Solution_oN2 {

        Set<String> set = new HashSet<>();

        public int countDistinct(String s) {

            for (int i = 0; i < s.length(); i++) {
                for (int j = i; j < s.length(); j++) {
                    set.add(s.substring(i, j + 1));
                }
            }

            return set.size();
        }

    }
}

All Problems

All Solutions