{"id":1080,"date":"2025-09-01T23:25:56","date_gmt":"2025-09-01T17:55:56","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=1080"},"modified":"2025-09-01T23:25:57","modified_gmt":"2025-09-01T17:55:57","slug":"count-distinct-substrings","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/count-distinct-substrings\/","title":{"rendered":"Count Distinct Substrings \u2013 Brute Force and Trie Approaches"},"content":{"rendered":"\n<p>The <strong>Count Distinct Substrings<\/strong> problem asks us to calculate the number of unique substrings of a given string.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A <strong>substring<\/strong> is a contiguous sequence of characters within a string.<\/li>\n\n\n\n<li>We must return the total count of distinct substrings, including the <strong>empty substring<\/strong>.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Examples<\/h3>\n\n\n\n<p><strong>Example 1<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input: s = &quot;ababa&quot;\nOutput: 10\nExplanation: Distinct substrings are \n&quot;a&quot;, &quot;b&quot;, &quot;ab&quot;, &quot;ba&quot;, &quot;aba&quot;, &quot;bab&quot;, &quot;abab&quot;, &quot;baba&quot;, &quot;ababa&quot;, &quot;&quot; (empty substring).\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">Input: s = <\/span><span style=\"color: #CE9178\">&quot;ababa&quot;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">Output: <\/span><span style=\"color: #B5CEA8\">10<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">Explanation: Distinct substrings are <\/span><\/span>\n<span class=\"line\"><span style=\"color: #CE9178\">&quot;a&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;b&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;ab&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;ba&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;aba&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;bab&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;abab&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;baba&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;ababa&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;&quot;<\/span><span style=\"color: #D4D4D4\"> (empty substring).<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p><strong>Example 2<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input: s = &quot;aaa&quot;\nOutput: 4\nExplanation: Distinct substrings are \n&quot;a&quot;, &quot;aa&quot;, &quot;aaa&quot;, &quot;&quot; (empty substring).\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">Input: s = <\/span><span style=\"color: #CE9178\">&quot;aaa&quot;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">Output: <\/span><span style=\"color: #B5CEA8\">4<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">Explanation: Distinct substrings are <\/span><\/span>\n<span class=\"line\"><span style=\"color: #CE9178\">&quot;a&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;aa&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;aaa&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;&quot;<\/span><span style=\"color: #D4D4D4\"> (empty substring).<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Intuition and Approach<\/h2>\n\n\n\n<p>We can solve this in two ways:<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Approach 1 \u2013 Brute Force with Set<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Generate all possible substrings of <code>s<\/code>.<\/li>\n\n\n\n<li>Store them in a set (to ensure uniqueness).<\/li>\n\n\n\n<li>Return the size of the set + 1 (to count the empty substring).<\/li>\n<\/ol>\n\n\n\n<p>This works but is inefficient for larger strings since substring generation is costly.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Code \u2013 Brute Force<\/h4>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"def countDistinctSubstrings(s):\n    n = len(s)\n    substrings = set()\n\n    # Generate all substrings\n    for i in range(n):\n        temp = &quot;&quot;\n        for j in range(i, n):\n            temp += s[j]\n            substrings.add(temp)\n\n    # +1 to include the empty substring\n    return len(substrings) + 1\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">countDistinctSubstrings<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">s<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(s)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    substrings = <\/span><span style=\"color: #4EC9B0\">set<\/span><span style=\"color: #D4D4D4\">()<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Generate all substrings<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp = <\/span><span style=\"color: #CE9178\">&quot;&quot;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(i, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp += s[j]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            substrings.add(temp)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># +1 to include the empty substring<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(substrings) + <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Dry Run \u2013 Brute Force<\/h4>\n\n\n\n<p>Input: <code>\"ababa\"<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>i = 0 \u2192 &#8220;a&#8221;, &#8220;ab&#8221;, &#8220;aba&#8221;, &#8220;abab&#8221;, &#8220;ababa&#8221;<\/li>\n\n\n\n<li>i = 1 \u2192 &#8220;b&#8221;, &#8220;ba&#8221;, &#8220;bab&#8221;, &#8220;baba&#8221;<\/li>\n\n\n\n<li>i = 2 \u2192 &#8220;a&#8221;, &#8220;ab&#8221;, &#8220;aba&#8221; (already counted)<\/li>\n\n\n\n<li>i = 3 \u2192 &#8220;b&#8221;, &#8220;ba&#8221; (already counted)<\/li>\n\n\n\n<li>i = 4 \u2192 &#8220;a&#8221; (already counted)<\/li>\n<\/ul>\n\n\n\n<p>Unique substrings = 9 + empty substring = 10.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Complexity \u2013 Brute Force<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong> O(N\u00b2) substrings \u00d7 O(N) for building strings = O(N\u00b3).<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong> O(N\u00b2) for storing substrings in a set.<\/li>\n<\/ul>\n\n\n\n<p>This approach is simple but not scalable for larger strings.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Approach 2 \u2013 Optimized Trie Solution<\/h3>\n\n\n\n<p>Instead of generating all substrings explicitly, we can:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Insert all <strong>suffixes<\/strong> of the string into a Trie.<\/li>\n\n\n\n<li>While inserting each suffix, count how many <strong>new nodes<\/strong> are created.\n<ul class=\"wp-block-list\">\n<li>Each new node corresponds to a <strong>new unique substring<\/strong>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Add <code>+1<\/code> for the empty substring.<\/li>\n<\/ol>\n\n\n\n<p>This avoids duplicate substrings automatically, since the Trie merges common prefixes.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Code \u2013 Trie Approach<\/h4>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class TrieNode:\n    def __init__(self):\n        self.children = {}\n\nclass Trie:\n    def __init__(self):\n        self.root = TrieNode()\n\n    def insert_and_count(self, word):\n        node = self.root\n        count_new_nodes = 0\n        for ch in word:\n            if ch not in node.children:\n                node.children[ch] = TrieNode()\n                count_new_nodes += 1\n            node = node.children[ch]\n        return count_new_nodes\n\ndef countDistinctSubstrings(s):\n    trie = Trie()\n    result = 0\n\n    # Insert all suffixes\n    for i in range(len(s)):\n        suffix = s[i:]\n        result += trie.insert_and_count(suffix)\n\n    # +1 for empty substring\n    return result + 1\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">TrieNode<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">__init__<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.children = {}<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Trie<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">__init__<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.root = TrieNode()<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">insert_and_count<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">word<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        node = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.root<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        count_new_nodes = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ch <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> word:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> ch <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">in<\/span><span style=\"color: #D4D4D4\"> node.children:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                node.children[ch] = TrieNode()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                count_new_nodes += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            node = node.children[ch]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> count_new_nodes<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">countDistinctSubstrings<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">s<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    trie = Trie()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    result = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Insert all suffixes<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(s)):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        suffix = s[i:]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result += trie.insert_and_count(suffix)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># +1 for empty substring<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> result + <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Dry Run \u2013 Trie Approach<\/h4>\n\n\n\n<p>Input: <code>\"ababa\"<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Insert suffix <code>\"ababa\"<\/code> \u2192 creates 5 new nodes.<\/li>\n\n\n\n<li>Insert suffix <code>\"baba\"<\/code> \u2192 creates 3 new nodes (overlaps with <code>\"ababa\"<\/code>).<\/li>\n\n\n\n<li>Insert suffix <code>\"aba\"<\/code> \u2192 creates 1 new node.<\/li>\n\n\n\n<li>Insert suffix <code>\"ba\"<\/code> \u2192 creates 1 new node.<\/li>\n\n\n\n<li>Insert suffix <code>\"a\"<\/code> \u2192 creates 0 new nodes (already exists).<\/li>\n<\/ul>\n\n\n\n<p>Total = 10 (including empty substring).<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Complexity \u2013 Trie Approach<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong> O(N\u00b2), since we insert N suffixes, each up to length N.<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong> O(N\u00b2), since at most all substrings could be stored in the Trie.<\/li>\n<\/ul>\n\n\n\n<p>Although both are O(N\u00b2), the Trie avoids building duplicate substrings and is significantly faster in practice compared to brute force.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p>The <strong>Count Distinct Substrings<\/strong> problem can be solved in two ways:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Brute Force (Set):<\/strong> Simple, but slow (O(N\u00b3)).<\/li>\n\n\n\n<li><strong>Trie Approach:<\/strong> Efficient, avoids duplicates naturally, and better suited for large inputs.<\/li>\n<\/ul>\n\n\n\n<p>The <strong>Trie-based solution<\/strong> is the optimal approach for this problem, leveraging prefix sharing to reduce redundant work.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Count Distinct Substrings problem asks us to calculate the number of unique substrings of a given string. Examples Example 1 Example 2 Intuition and Approach We can solve this in two ways: Approach 1 \u2013 Brute Force with Set This works but is inefficient for larger strings since substring generation is costly. Code \u2013<\/p>\n","protected":false},"author":1,"featured_media":1081,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[19,44],"class_list":{"0":"post-1080","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-medium","10":"tag-tries"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/09\/count-distinct-substrings-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1080","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=1080"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1080\/revisions"}],"predecessor-version":[{"id":1082,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1080\/revisions\/1082"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/1081"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=1080"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=1080"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=1080"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}