[Java] Clean Solution || with detailed explanation
The key to solve this problem is cleverly enumerate all numbers < n without repeated digits. One of the ways is as follow: \n\nStep 1 : count numbers with lengt
The key to solve this problem is cleverly enumerate all numbers < n without repeated digits. One of the ways is as follow: \n\n**Step 1 : count numbers with length smaller than n:**\n```\n// return count of numbers with d digits and no repeated digits\nprivate int totalNoRepeat(int d) {\n\tint res = 9;                         // 0-th digit has 9 choices (1, ..., 9)\n\t\n\t/* 1-st digit has 9 choices         <==>  (0, ..., 9) except 0-th digit\n\t   2-st digit has 8 choices         <==>  (0, ..., 9) except 0-th & 1-st digit\n\t                              ...\n\t   i-th digit has (10- i) choices   <==>  (0, ..., 9) except 0-th & ...&  (i-1)-th digit      */\n\t\n\tfor (int i = 1; i < d; i++) {\n\t\tres *= (10 - i);                 \n\t} \n\treturn res;\n}\n```\n**Step 2 : count numbers with length equals to n:**\n```\nCase 1 :  n = 3 4 6 5     \n\tpivot index i = 0 should < 3                                                <==> {1, 2} \n\t\t\t\t\t1 X X X - 2 X X X    ==>  2 * 9 * 8 * 7\n    pivot index i = 1 should < 4  and not take values of previous indices       <==> {0, 1, 2} \n\t\t\t\t\t3 0 X X - 3 3 X X    ==>  1 * 3 * 8 * 7 \n\tpivot index i = 2 should < 6  and not take values of previous indices       <==> {0, 1, 2, 5} \n\t\t\t\t\t3 4 0 X - 3 4 5 X    ==>  1 * 1 * 4 * 7\n    pivot index i = 3 should < 5  and not take values of previous indices       <==> {0, 1, 2} \n\t\t\t\t\t3 4 6 0 - 3 4 6 5    ==>  1 * 1 * 1 * 3\n\nCase 2 :  n = 3 3 5 3\n\tpivot index i = 0 should < 3                                                <==> {1, 2} \n\t\t\t\t\t1 X X X - 2 X X X    ==>  2 * 9 * 8 * 7\n\tpivot index i = 1 should < 3  and not take values of previous indices       <==> {0, 1, 2} \n\t\t\t\t\t3 0 X X - 3 2 X X    ==>  1 * 3 * 8 * 7\n\tpivot index i = 2  and after should not be consider\n\t\t\t\t\t3 3 X X              ==>  0  the number will contain repeated digits\n```\nFrom these two examples, we can see the pattern of choosing digits: \n```\n// i := pivot index       \n// d := i-th digit in the original number n\n\ni = 0     <==>  choose from {1, 2, ..., d-1};  After the pivot index i = 0: \n\t// 1-st digit has 9 choices         <==>  (0, ..., 9) except  {0-th digit}\n\t// 2-nd digit has 8 choices         <==>  (0, ..., 9) except  {0-th, 1-st digit}\n\t//                 ...\n\ni = 1     <==>  choose from {0, 1, ... , d-1} - {0-th digit};  After the pivot index i = 1: \n\t// 2-nd digit has 8 choices         <==>  (0, ..., 9) except  {0-th, 1-st digit}\n\t// 3-rd digit has 7 choices         <==>  (0, ..., 9) except  {0-th, 1-st, 2-nd digit}\n\t//                 ...\n\nThus for j-th digit after the pivot index i,  \n\t// j-th digit has (10- j) choices   <==>  (0, ..., 9) except 0-th & ...&  (j-1)-th digit      \n```\n\n**Final solution:** \n```\nclass Solution {\n    public int numDupDigitsAtMostN(int n) {\n        String str = String.valueOf(n);\n        int len = str.length();\n        \n        // all number with no repeat and length < len\n        int unique = 0;\n        for (int i = 1; i < len; i++) {\n            unique += totalNoRepeat(i);\n        }\n        \n\t\t// all number with no repeat and length == len\n        Set<Integer> set = new HashSet<>();\n        int i = 0;\n        for (i = 0; i < len; i++) {\n            int d = str.charAt(i) - \'0\';\n            \n            int temp = pivotChoice(set, d, i == 0);\n            for (int j = i+1; j < len; j++) {\n                temp *= (10 - j);\n            }\n            \n            unique += temp;\n            if (!set.add(d)) break;       // no need to continue after seeing repeated digits\n        }\n        \n        if (i == len) unique++;      // the number n itself\n        \n        return n - unique;\n    }\n    \n    private int totalNoRepeat(int d) {\n        int res = 9;\n        for (int i = 1; i < d; i++) {\n            res *= (10 - i);\n        }\n        return res;\n    }\n    \n    private int pivotChoice(Set<Integer> set, int d, boolean first) {\n        int res = 0;\n        int i = (first ? 1 : 0);\n        \n        while (i < d) {\n            if (!set.contains(i++)) res++;\n        }\n        \n        return res;\n    } \n    \n}\n```\n\nThe main function can also be written as following. Here we consider the count of numbers strictly less than (n+1):\n\n```\npublic int numDupDigitsAtMostN(int n) {\n\tString str = String.valueOf(n+1);\n\tint len = str.length();\n\t\n\tint unique = 0;\n\tfor (int i = 1; i < len; i++) {\n\t\tunique += totalNoRepeat(i);\n\t}\n\n\tSet<Integer> set = new HashSet<>();\n\tint i = 0;\n\tfor (i = 0; i < len; i++) {\n\t\tint d = str.charAt(i) - \'0\';\n\n\t\tint temp = pivotChoice(set, d, i == 0);\n\t\tfor (int j = i+1; j < len; j++) {\n\t\t\ttemp *= (10 - j);\n\t\t}\n\n\t\tunique += temp;\n\t\tif (!set.add(d)) break;      \n\t}\n\treturn n - unique;\n}\n```
['Java']