## Groupon Interview Question

Software Developers**Country:**United States

With a string of length n, you have 2 in power of (n-1) different possible coma delimited strings. You can represent state of coma positions as an array of 0s and 1s, where 1 means that comma is needed at i+1 position. In this example: 123, would have the following:

```
0,0 => 123
0,1 => 12,3
1,0 => 1,23
1,1 => 1,2,3
```

the way you do it is you need introduce a variable of type

`int k;`

and increment it by 1 at each cycle, until

`k<input.length-1`

. To check whether the coma is needed you need to check condition:

`(k>>1)&1==1`

The problem is numbers greater than 26 cannot be encoded. Thus 893 can only be encoded as 8,9,3 and no three digit numbers are allowed. I feel like recursion would be useful here as it would allow to not have to check "unallowed" permutations more than once at each level.

```
1,2,2,2
12,2,2
1,22,2
then
12,22
1,2,22
```

Adding a 5th is all of the above encodings plus

```
1,2,2,22
12,2,22
1,22,22
```

which happens to be the 3 digit encodings

6 gives all of the above plus

```
1,2,2,2,22
1,22,2,22
12,2,2,22
1,2,22,22
12,22,22
```

Which once again is all the 4 digit encodings

Thus the number of encodings for a N digit string(where every combination can encoded) is the number of encodings for an n-1 digit string + the number of encodings of a n-2 digit string. Note if every combination is not possible, such as 12,35 then make sure you check that each number is < 26 or else don't count it.

I would definitely use a dynamic programming approach or else this will become exponential in run time like fibonacci.

```
public static int findNumberOfDecodeSequences(String sequence) {
if(sequence.length() == 0) {
return 0;
}
int numStringsEndingWithSingleDigit = 1;
int numStringsEndingWithDoubleDigits = 0;
for(int i = 1; i < sequence.length(); i++) {
int doubleDigitVal = (sequence.charAt(i - 1) - '0') * 10 + (sequence.charAt(i) - '0');
if(doubleDigitVal <= 26) {
int temp = numStringsEndingWithDoubleDigits + numStringsEndingWithSingleDigit;
numStringsEndingWithDoubleDigits = numStringsEndingWithSingleDigit;
numStringsEndingWithSingleDigit = temp;
}
else {
numStringsEndingWithSingleDigit = numStringsEndingWithSingleDigit + numStringsEndingWithDoubleDigits;
numStringsEndingWithDoubleDigits = 0;
}
}
return (numStringsEndingWithDoubleDigits + numStringsEndingWithSingleDigit);
}
```

```
public static int findNumberOfDecodeSequences(String sequence) {
if(sequence.length() == 0) {
return 0;
}
int numStringsEndingWithSingleDigit = 1;
int numStringsEndingWithDoubleDigits = 0;
for(int i = 1; i < sequence.length(); i++) {
int doubleDigitVal = (sequence.charAt(i - 1) - '0') * 10 + (sequence.charAt(i) - '0');
if(doubleDigitVal <= 26) {
int temp = numStringsEndingWithDoubleDigits + numStringsEndingWithSingleDigit;
numStringsEndingWithDoubleDigits = numStringsEndingWithSingleDigit;
numStringsEndingWithSingleDigit = temp;
}
else {
numStringsEndingWithSingleDigit = numStringsEndingWithSingleDigit + numStringsEndingWithDoubleDigits;
numStringsEndingWithDoubleDigits = 0;
}
}
return (numStringsEndingWithDoubleDigits + numStringsEndingWithSingleDigit);
}
```

public static int decodeSeq(String num) {

if (num.length() == 0)

return 0;

int[] f = new int[num.length() + 1];

f[0] = 1;

f[1] = 1;

for (int i = 1; i < num.length(); i++) {

if ((num.charAt(i - 1) - '0') * 10 + (num.charAt(i) - '0') <= 26) {

f[i + 1] = f[i] + f[i - 1];

} else {

f[i + 1] = f[i];

}

}

return f[num.length()];

}

public static int decodeSeq(String num) {

if (num.length() == 0)

return 0;

int[] f = new int[num.length() + 1];

f[0] = 1;

f[1] = 1;

for (int i = 1; i < num.length(); i++) {

if ((num.charAt(i - 1) - '0') * 10 + (num.charAt(i) - '0') <= 26) {

f[i + 1] = f[i] + f[i - 1];

} else {

f[i + 1] = f[i];

}

}

return f[num.length()];

}

DP

```
package Java;
import java.util.Arrays;
/**
* Author: Nitin Gupta
* Date: 26/04/19
* Description:
*/
public class NumberOfWaysToDecodeDigitSeq {
public static void main(String args[]) {
String s = "1212";
System.out.println(ways(s));
}
private static int ways(String s) {
if (s == null || s.isEmpty())
return 0;
int n = s.length();
int count[] = new int[n + 1];
Arrays.fill(count, 0);
count[0] = 1; //every single character can be transform
count[1] = 1;
char digits[] = s.toCharArray();
for (int i = 2; i <= n; i++) {
if (digits[i - 1] > '0')
count[i] += count[i - 1];
if (digits[i - 2] == '1' || digits[i - 2] == '2' && digits[i - 1] < '7')
count[i] += count[i - 2];
}
return count[n];
}
}
```

- Anonymous June 08, 2015