Assume there are no duplicate characters and there is target string "ABCD"
How many permutations are there of this same string such that there exists a substring of at least two characters?
Examples for "ABCD": ABDC, CDAB, DBCA
Is there a general formula to solve this? Using a backtracking algorithm I get the following numbers for a string of size n:
- n = 1 -> 0
- n = 2 -> 1
- n = 3 -> 3
- n = 4 -> 13
- n = 5 -> 67
- n = 6 -> 411
Originally I thought something like (N-1)^2 * (N - 2) for a string of size N because there can exist at most N-1 two consecutive characters that are a substring and they can be placed N-1 ways. Then there are N - 2 ways to place the remaining characters. This is incorrect as there can be more than one substring within same string (e.g. CDAB). Would appreciate any thoughts, thanks!