Alphanumeric Abbreviations of a String

Given a string s, return all the alpha-numeric abbreviation of the string.

The alpha-numeric abbreviation is in the form of characters mixed with the digits which is equal to the number of skipped characters of a selected substring.

Whenever a substring of characters is skipped, replace it with the digit denoting the number of characters in the substring. There may be any number of skipped substrings of a string. No two substrings should be adjacent to each other. Hence, no two digits are adjacent in the result.

Input Format:

First Parameter: String s

Output Format:

Return an array of strings

Example 1

Input: 
ANKS
Output: 
ANKS (nothing is replaced)
ANK1 (S is replaced) 
AN1S (K is replaced)
AN2  (KS is replaced)
A1KS (N is replaced)
A1K1 (N and S are replaced)
A2S (NK is replaced)
A3 (NKS is replaced)
1NKS (A is replaced)
1NK1 (A and S are replaced)
1N1S (A and N is replaced)
1N2 (A and KS are replaced)
2KS (AN is replaced)
2K1 (AN and S is replaced)
3S (ANK is replaced)
4 (ANKS is replaced)

Example 2

Input: 
ABC
Output: 
ABC
AB1 
A1C 
A2 
1BC 
1B1 
2C 
3
Note: 11C is not valid because no two digits should be adjacent, 
2C is the correct one because AB is a substring, not A and B individually

Constraints

• n = s.length
• 1 <= n < 10
• s contains both uppercase and lower case characters
• Expected Time Complexity - O(2^n)
• Expected Space Complexity - O(n)