_1698. Number of Distinct Substrings in a String.md

1698. Number of Distinct Substrings in a String

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 02, 2024

Last updated : July 01, 2024

---

Related Topics : String, Trie, Rolling Hash, Suffix Array, Hash Function

Acceptance Rate : 64.13 %

---

Solutions

• m1698 v1.java
• m1698 v1.py

Java

m1698 v1.java

// Same as v1 python just using Java

class Solution {
    private HashSet<String> visited = new HashSet<>();
    public int countDistinct(String s) {
        helper(s);
        return visited.size();
    }

    private void helper(String s) {
        if (visited.contains(s) || s.length() == 0) {
            return;
        }

        visited.add(s);
        helper(s.substring(1));
        helper(s.substring(0, s.length() - 1));
    }
}

Python

m1698 v1.py

# Inefficient brute force solution using high memory and sets but works

class Solution:
    def countDistinct(self, s: str) -> int:
        outputSet = set()
        def helper(sub: str):
            if sub in outputSet :
                return 
            outputSet.add(sub) 
            
            helper(sub[1:]) 
            helper(sub[:-1])

        helper(s)
        return len(outputSet) - 1
        
        
# Slightly less efficient option: 

# class Solution:
#     def countDistinct(self, s: str) -> int:
#         outputSet = set()
#         def helper(sub: str) -> int :
#             if sub in outputSet :
#                 return 0
#             outputSet.add(sub) 
            
#             return 1 + helper(sub[1:]) + helper(sub[:-1])

#         return helper(s) - 1