Java | Tabulation | Explained
Method 1 \n Every character generates 2x subsequences generated till its previous character because you can either include or exclude this char\n To avoid dupli
**Method 1** \n* Every character generates 2x subsequences generated till its previous character because you can either include or exclude this char\n* To avoid duplicates, remove the subsequences generated till the char before the previous occurrence of this char because all those subsequences will be generated again by the repeated occurrence of the char\n>T/S: O(n)/O(n), where n = size(s)\n```\nprivate static final int MOD = (int) (1e9 + 7);\n\npublic int distinctSubseqII(String s) {\n\tvar n = s.length();\n\tvar dp = new int[n + 1];\n\tvar lastIndex = new HashMap<Character, Integer>();\n\tdp[0] = 1;\n\n\tfor (var i = 1; i <= n; i++) {\n\t\tvar ch = s.charAt(i - 1);\n\t\tdp[i] = 2 * dp[i - 1] % MOD;\n\n\t\tif (lastIndex.containsKey(ch))\n\t\t\tdp[i] = (dp[i] - dp[lastIndex.get(ch) - 1]) % MOD;\n\n\t\tlastIndex.put(ch, i);\n\t}\n\n\n\tif (--dp[n] < 0)\n\t\tdp[n] += MOD;\n\n\treturn dp[n] % MOD;\n}\n```\n\n**Method 2** \n>T/S: O(n)/O(1)\n```\npublic int distinctSubseqII(String s) {\n\tvar subsEndingAtChar = new HashMap<Character, Integer>(); \n\tvar totalSubs = 1; //Empty string, starting at count 1\n\n\tfor (var i = 0; i < s.length(); i++) {\n\t\tvar ch = s.charAt(i);\n\t\tvar subsEndingHere = 2 * totalSubs - subsEndingAtChar.getOrDefault(ch, 0); \n\t\tsubsEndingAtChar.put(ch, totalSubs);\n\n\t\tif (subsEndingHere < 0)\n\t\t\ttotalSubs = subsEndingHere + MOD;\n\t\telse\n\t\t\ttotalSubs = subsEndingHere % MOD;\n\t}\n\n\tif (--totalSubs < 0)\n\t\ttotalSubs += MOD;\n\n\treturn totalSubs;\n}\n```\n***Please upvote if this helps***
['Java']