Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 6 vote

DP solution

``````public static int getCombinationsNumber(String s){
if (s.length() == 0)
return 0;
int[] dp = new int[s.length()];
dp[0] = 1;
for (int i = 1 ; i < s.length() ; i++){
int num = (s.charAt(i-1) - '0') * 10 + (s.charAt(i) - '0');
if (dp[i-1] != 0) {
dp[i] += dp[i - 1];
}
if (num <= 25) {
dp[i] += i == 1 ? 1 : dp[i - 2];
}
}
return dp[s.length()-1];
}``````

If you wish, you can optimize it to use O(1) memory.

Comment hidden because of low score. Click to expand.
0

can any body explain this code? What is the overlapping problem of the subproblem. More precisely, why {dp[i-2] + d[i-1]} gives out the combination number for d[i]?

Comment hidden because of low score. Click to expand.
0

You can check my explanation and the O(1) space solution below.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````def numStrings(s, n):
if n == 0:
return 0
if n == 1:
return 1

if n == 2:
num = int(s[n-1] * 10) + int(s[n])
s = ( num >=10 and num <=25)? 3 : 2
return s

else:
num = int(s[n-1] * 10) + int(s[n])
s = (num >=10 and num <=25)?1 : 2
return s  + numStrings(s, n-2)``````

At any pt i where i > 1, you have a chance to consider char at i-1 and i together if they form a number between 10 and 25 both inclusive, if so then you have one extra string along with 2 others formed by single chars at i-1 and i, to which you will add strings formed at i-2. If you draw out the recursion tree you can see that there are overlapping calls which ultimately leads to the DP soln above

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````def numStrings(number):
n = len(number)
print "n is: ", n
if n == 0:
return 0

elif n == 1:
return 1

elif n == 2:
num = int(number[-2])* 10 + int(number[-1])
s = 3 if (num >=10 and num <= 25) else 2
print "num  now: ", num
print "s is: ", s
return s

else:
num = int(number[-2])* 10 + int(number[-1])

s = 3 if (num >=10 and num <=25) else 2
print "num  now: ", num
print "s is: ", s
return (s  + numStrings(number[:-1]))``````

Improved the code above a bit

Comment hidden because of low score. Click to expand.
0

Need explanation!!!

Comment hidden because of low score. Click to expand.
0

@Anonymous and @saurav: I don't agree with your solution

if string = "25", you can either generate "CF" or "Z", => you suggested 3
if string = "55", you can only generate "FF",=> you suggested 2

I don't think the questions is asking for sub-strings, if you want to consider sub-strings, then you have to count the number of distinct strings,

Am I missing something here?

Comment hidden because of low score. Click to expand.
0

I'm afraid the answers given are wrong,
consider the string "11111" (5 characters), here are the strings you can generate:

1- "BBBBB"

2- "BBBL"
3- "BBLB"
4- "BLBB"
5- "LBBB"

6- "BLL"
7- "LBL"
8- "LLB"

NONE OF THE ANSWERS ABOVE GENERATES THIS

Comment hidden because of low score. Click to expand.
0

This solution clearly does not have an optimal substructure because it ignores the presence of duplicate characters when using the smaller substring to obtain the count for a larger substring. It would only work if all characters were unique.

Comment hidden because of low score. Click to expand.
0

This solution clearly does not work because it does not have an optimal substructure. It fails every time the string has duplicate characters.

Comment hidden because of low score. Click to expand.
0

Tested with a very basic sample: "123" your solution returns 3, but shouldn't it be: 5? - 1 = B, 2 = C, 3 = D, 12 = M and 23 = X ?

Comment hidden because of low score. Click to expand.
0

Your solution is correct for all cases except handling 0s. 0 cannot be joined with another digit (01 is just AB and not A). So you have to handle the case

``s.charAt(i-1) == '0'``

separately.

Comment hidden because of low score. Click to expand.
1
of 1 vote

We will use dynamic programming by creating an int[] count array, where each element, count[i], stores the number of strings we can make with a substring starting from i. For example, input = "01234", count[3] = # of diff strings of "34", count[2] = # of diff string of "234".

To find count[0], we use a the following relationship:
Number of different string of "1234" = number of different string of "234" + number of different string of "34" if "12" is in the mapping lookup table.

Let LU be the lookup table containing the keys, and let N = input length. Then, initialize count[N] = 1, count[N-1] = 1 and follow the relationship
count[i] = count[i+1] + LU.containsKey(input.substring[i, i+2])? count[i+2]: 0;
Loop through i from N-2 to 0.
Finally, count[0] is what we are looking for.

Comment hidden because of low score. Click to expand.
1
of 1 vote

here is the c++ code

``````int CountStrings( char * s, int n )
{
if ( n < 2 )
{
return 1;
}

int number = (s[n-1]-'0') + (s[n-2]-'0')*10;

if ( ( number >= 10 ) && ( number <= 25 ) )
{
return CountStrings( s, n-1 ) + CountStrings( s, n-2 );
}
else
{
return CountStrings( s, n-1 );
}
}``````

Comment hidden because of low score. Click to expand.
0

``````int CountStrings( char * s, int n )
{
if ( n < 2 )
{
return 1;
}

int number = (s[n-1]-'0') + (s[n-2]-'0')*10;

if ( ( number >= 10 ) && ( number <= 25 ) )
{
return CountStrings( s, n-1 ) + CountStrings( s, n-2 );
}
else
{
return CountStrings( s, n-1 );
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@koosha.nejad I guess your solution is missing a 1 + before the recurrence please see my solution in java.

Comment hidden because of low score. Click to expand.
0
of 2 vote

This is a linear combinatorics question

given 2 digit numbers that are > 10 and < 25 for example, count the number of adjacent numbers:

it becomes a n choose k. What that means is for a string of 22222 the number of combinations is 5 choose 2 (since there's 2 possibilities for each pair).

given that information the problem becomes easier to understand.

Step 1: iterate through the string by pairs for instance:
[22]222 -> 2[22]222
count the number of continuos pairs >10 < 25 and store them in a hashmap. So you would have the key be the n in (n choose 2) and the value is the number of times the continuous pair has been seen.

At the end, iterate over the hash map and add all the numbers ignoring singles.

Example:

2205022

220 = 3 choose 2
22 = 2 (because there's 2 values here)

So the answer is 7 for that example string

Comment hidden because of low score. Click to expand.
1
of 1 vote

Shouldn't it be 6, how it is 7?

Comment hidden because of low score. Click to expand.
0

I disagree

consider the string "11111" (5 characters), the solution is 8, 5 choose 2 is 10

1- "BBBBB"

2- "BBBL"
3- "BBLB"
4- "BLBB"
5- "LBBB"

6- "BLL"
7- "LBL"
8- "LLB"

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int noOfStringsFromIntegerString(String s,int index,int length)
{   int count =0;
if(index+1>=length)
count = 1;
else {
count = noOfStringsFromIntegerString(s, index+1, length);
int temp = Integer.parseInt( s.substring(index,index+2));
if(temp < 26){
count += noOfStringsFromIntegerString(s, index+2, length);
}
}
return count;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think you have a mistake because you also consider the case that numbers can also be written in the form 03, 04, 05... I don't suppose that this is the case. To avoid this stuff you should add the statement

``Integer.parseInt(s.substring(index, index + 1)) > 0``

into your "if" which checks if temp is less than 26.

Comment hidden because of low score. Click to expand.
0

I believe you should replace "if(temp < 26)" with "if(temp < 26) && (temp>=10)"

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int noOfStringsFromIntegerString(String s,int index,int length)
{   int count =0;
if(index+1>=length)
count = 1;
else {
count = noOfStringsFromIntegerString(s, index+1, length);
int temp = Integer.parseInt( s.substring(index,index+2));
if(temp < 26){
count += noOfStringsFromIntegerString(s, index+2, length);
}
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ DP solutions with O(n) space and O(1) space

``````// O(n) time, O(n) space
int CountPossibleStrings(const string &s) {
vector<int> cnt(s.size()+1, 1);
for (int i = s.size()-2; i >= 0; --i) {
cnt[i] = cnt[i+1];
if (s[i] == '1' || (s[i] == '2' && s[i+1] <= '5'))
cnt[i] += cnt[i+2];
}
return cnt[0];
}

// O(n) time, O(1) space
int CountPossibleStringsO1Space(const string &s) {
int cnt[] = {1, 1}, slot = 0;
for (int i = s.size()-2; i >= 0; --i, ++slot) {
int v = cnt[slot%2];
if (s[i] == '1' || (s[i] == '2' && s[i+1] <= '5'))
v += cnt[(slot+1)%2];
cnt[(slot+1)%2] = v;
}
return cnt[slot%2];
}``````

Comment hidden because of low score. Click to expand.
0

s[i]==1 and s[i+1]==9 is acceptable, but your code doesn't allow it

Comment hidden because of low score. Click to expand.
0
of 0 vote

Perform DFS via reursion or stack. At each step on can either (i) use one digit or (ii) use two digits to map to char. Well not actually, be careful because two digits can be used if and only if the first digit is 1 or if the first digit is 2 and the following is 0-5.
A sample code is shown below:

``````public int howMany(String s) {
return howMany(s, 0);
}
private int howMany(String s, int k) {
int N = s.length();
if (k >= N)			return 0;
int cnt = 1;

cnt += howMany(s, k+1);
if (k == N-1) 			return cnt;

char c = s.charAt(k);
char d = s.charAt(k+1);
if (c == '1' || (c == '2' && d <= '5'))
cnt += howMany(s, k+2);

return cnt;
}``````

Comment hidden because of low score. Click to expand.
0

c=='1' and d=='9' is acceptable, but your code doesn't allow it

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a non-recursive version:
Based on this function

``````f(n)(k) means
for a string of length n in which any adjacent character are combinable,
the solution number of splitting it so that there k substring with a pair of character while others of one character.
Then.
f(n)(0) = 1
f(n)(1) = n-1
f(n)(k) = f(n-2)(k-1) + f(n-3)(k-1) + ... + f(2k-2)(k-1)
f(n)(n/2) = 1 if n is oven else f[l-2][l/2-1]

This is a simple implementation:

#The string can be divided into 'super substring'
# 11111121, is a kind of super substring
# any adjacent unit in super substring is combinable.

#calculate all possible combination of super_substring

data_dict = {1:[1]}

# l is length of super substring
def solv_super_substring(l):
if l <= 1:
return
data_dict[l] = [0] * (l/2+1)
data_dict[l][0] = 1
data_dict[l][1] = l-1
for i in xrange(2, l/2):
for j in xrange((i-1)*2, l-1):
data_dict[l][i] += data_dict[j][i-1]

if l % 2 == 1:
data_dict[l][l/2] = 1+data_dict[l-2][l/2-1]
else:
data_dict[l][l/2] = 1

def extract_super_substring(s):
ssstr = []

tmp = ''
lofs = len(s)
for c in xrange(lofs):
if s[c] in '12':
tmp += s[c]
continue
elif s[c] in '3456' and len(tmp) > 0:
tmp += s[c]
ssstr.append(tmp)
tmp = ''
return ssstr

#test
if __name__ == '__main__':
s = '123121241291'
sstr = extract_super_substring(s)
print s
print sstr

lofss = map(lambda x: len(x), sstr)
ml = max(lofss)
for i in xrange(ml+1):
solv_super_substring(i)
print data_dict

res = []
for l in lofss:
res.append(sum(data_dict[l]))
print res
r = 1
for i in res:
r *= i
print r``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int getCount( String num , int k ){

if(num.length() <= k )
return 0;

int count = getCount( num ,k+1 ) ;
if( num.charAt(k) ==1 || (num.charAt(k) == 2 && num.charAt(k+1) <= 5))
count += 1 + getCount( num ,k+2 );

return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def countPossibleStrings(str):
strNumSoFar = [0 for i in xrange(0, len(str))]
for i in xrange(0, len(str)):
if (i > 0):
if (strNumSoFar[i-1] > 0):
strNumSoFar[i] += strNumSoFar[i-1]
else:
strNumSoFar[i] = 1
if (i > 1):
if (strNumSoFar[i-2] > 0 and int(str[i-1]) > 0 and int(str[i-1])*10 + int(str[i])< 26):
strNumSoFar[i] += strNumSoFar[i-2]
else:
if (i > 0):
if (int(str[i-1]) > 0 and int(str[i-1])*10 + int(str[i]) < 26):
strNumSoFar[i] += 1
print strNumSoFar[len(str) - 1]

countPossibleStrings("132493820173849029382910382")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int countStrings(String string) {
if("".equals(string) || (string == null)) {
return 0;
} else if(string.length() == 1) {
return 1;
} else {
int twoDigits = Integer.valueOf(string.substring(0, 2));
if((twoDigits >= 10) && (twoDigits <= 25)) {
return 1 + countStrings(string.substring(1)) + countStrings(string.substring(2));
} else {
return 1 + countStrings(string.substring(1));
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int decode(string &s){
if(s.empty()) return 0;
int pre=1, cur=1;
for(int i=1; i<s.length(); ++i){
int t=cur;
if(s[i-1]=='1' || s[i-1]=='2' && s[i]<='5')
cur+=pre;
pre=t;
}
return cur;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 1 -> B
// 13 -> BD, N
// 132 -> BDC, NC
// 112  -> BBC, LC, BM
def stringFinder(s:String):List[String] = {

// convert integer String to a letter
val is2letter: String => String =  (si:String) =>('a' + si.toInt).asInstanceOf[Char].toString

implicit def cToS(c:Char):String = c.toString

if(s.length == 1) {
List(is2letter(s))
}else if(s.length == 2){
val s1 =  is2letter(s(0)) + is2letter(s(1))
val s2:String = s match{
case a if a.toInt >= 'a'-'a' && a.toInt <= 'z'-'a'=> is2letter(a)
case _ =>""
}
if(!s2.isEmpty) List(s1,s2) else List(s1)

} else {

var results = List[String]()
val s0 = is2letter(s(0))
for(_s:String <- stringFinder(s.tail)) {
results = (s0+_s) :: results
}

if(s0 != "a") {
s.substring(0,2) match{
case a if a.toInt >= 'a'-'a' && a.toInt <= 'z'-'a'=> {
val s1 = is2letter(a)
for(_s:String <-stringFinder(s.tail.tail)) {
results = (s1+_s) :: results
}
}
case _ =>""
}
}

results
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementations

int CountOfPossible(string input)
{
if (String.IsNullOrWhiteSpace(input))
{
return 0;
}

int count = input.Length; // each number corresponds to letters

for (int i = 0; i < input.Length - 2; i++)
{
string sub = input.Substring(i, 2);

int num = ConvertToNum(sub);
if (10 <= num && num <= 25) // the two digits neighbors
{
count++;
}
}
return count;
}

int ConvertToNum(string input)
{

int parsedInt = -1;

int.TryParse(input, out parsedInt);

return parsedInt;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.Map;
import java.util.TreeMap;

public class StringCounter {

private Map<String, Character> myMap;

public StringCounter() {
myMap = new TreeMap<String, Character>();
//Builds the map: 0 -> A, ..., 25->Z
for(int i = 0; i < 26; i++) {
myMap.put(i+"", (char) (i+65));
}
}

//slow recursive strategy.
public int countStrings(String input) {
if(input.isEmpty()) return 1;

int num = countStrings(input.substring(1));
if(input.length() >=2 && myMap.containsKey(input.substring(0, 2)))
num += countStrings(input.substring(2));

return num;
}

//DP Soln - O(n) space, O(n) time
public int countStringsDP(String input) {
int[] numStrings = new int[input.length()];
numStrings[0] = 1;
numStrings[1] = myMap.containsKey(input.substring(0,2)) ? 2 : 1;
for(int i = 2; i < input.length(); i++) {
numStrings[i] = numStrings[i-1];
if(myMap.containsKey(input.substring(i-1, i+1)))
numStrings[i] += numStrings[i-2];
}
return numStrings[input.length()-1];
}

//DP Soln - O(n) time, constant space
public int countStringsDP2(String input) {
int val1 = 1;
int val2 = myMap.containsKey(input.substring(0,2)) ? 2 : 1;
for(int i = 2; i < input.length(); i++) {
int temp = val2;
if(myMap.containsKey(input.substring(i-1, i+1)))
temp += val1;
val1 = val2;
val2 = temp;
}
return val2;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with Fibonacci Terms:

Sequences for continuous two digit matching numbers can be broken down as Fibonacci term, and the final result is the multiplication of each such terms.

Example:
11 -> 2 F(3)
111 -> 3 F(4)
1111 -> 5 F(5)
11111 -> 8 F(6)
.....
......
n consecutive -> F(n-1)

so, 110511 -> F(4)*F(3) = 3*2 = 6

Here are the 6 variations:
BBAFBB
LAFBB
BKFBB
BBAFL
LAFL
BKFL

Here is the O(n) time and O(1) space solution

``````int getVariation(char* array)
{
int retVal = 1;
int len = strlen(array);
int prevSum=1, currSum=1;

for (int i=0; i< len; i++)
{
int twoDigitNum = -1;
if( i>0 && array[i-1] > '0')
{
twoDigitNum = (array[i-1]-'0')*10 + array[i] - '0';
}

if (twoDigitNum >=10 && twoDigitNum <=25)
{
int tmp = currSum;
currSum += prevSum;
prevSum = tmp;
}
else
{
retVal *= currSum;
currSum = 1;
prevSum = 1;
}
}

retVal *= currSum;
return retVal;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

110511 -> List(lafl, lafbb, bbafbb, bbafl, bkfl, bkfbb)

Comment hidden because of low score. Click to expand.
0

Hello could you please elaborate because i am having difficulty understanding your logic. I would like to know what those 1s mean

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static char[] getChars(String s) {
char[] charsExists = new char[26];

if (s == null)
return charsExists;
else if (s.length() < 2) {
charsExists[Character.getNumericValue(s.charAt(0))] = (char) ((65 + Character
.getNumericValue(s.charAt(0))));
} else {
for (int i = 0; i < s.length(); i++) {
if (charsExists[Character.getNumericValue(s.charAt(i))] == '\u0000') {
charsExists[Character.getNumericValue(s.charAt(i))] = (char) ((65 + Character
.getNumericValue(s.charAt(i))));
/* System.out.println(" 1 :"
+ Character.getNumericValue(s.charAt(i)));*/
} else {
System.out.println("character Exists + "
+ String.valueOf(s.charAt(i)));
}
// int num = Character.getNumericValue(s.charAt(i) + s.charAt(i
// + 1));
if (i != s.length() - 1) {
int num = Integer.parseInt(s.substring(i, i + 2));

//System.out.println("2 :" + num);
if (num < 26 && charsExists[num] == '\u0000') {

charsExists[num] = (char) (65 + num);
} else {
System.out
.println("character Exists or not valid number: "
+ num);
}
}
}

}

return charsExists;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def count(s):
n_ways = [0 for _ in xrange(len(s) + 1)]
n_ways[len(s)] = n_ways[len(s) - 1] = 1
idx = len(s) - 2
while idx >= 0:
n_ways[idx] = n_ways[idx+1]
a, b = int(s[idx]), int(s[idx]+1)
number = a * 10 + b
if number <= 25:
n_ways[idx] += n_ways[idx+2]
idx -= 1
return n_ways[0]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be solved in O(n) time, both recursively and iteratively. Here is an iterative version:

``````import java.util.Scanner;

class NumToString {
public static void main (String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Enter the Number-string");
String str = s.nextLine();
char [] cArray = str.toCharArray();
int [] array = new int[str.length()];
for (int i = 0; i < array.length; i++) {
if (cArray[i] >= '0' && cArray[i] <= '9') {
array[i] = cArray[i] - '0';
}
else {
System.err.println("Wrong input. Exiting...");
}
}
int [] memArray = new int[array.length + 1];
memArray[array.length] = 1;
memArray[array.length - 1] = 1;
for (int i = array.length - 2; i >= 0; i--) {
if (array[i] > 2 || array[i] == 0 || (array[i] == 2 && array[i + 1] > 5)) {
memArray[i] = memArray[i + 1];
}
else {
memArray[i] = memArray[i + 1] + memArray[i + 2];
}
}
System.out.println("Number of strings possible = " + memArray[0]);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int get_combination_num(char* s) {
if (s == NULL) return -1;
int str_len = strlen(s);
if (str_len == 0) return 0;

int* dp = (int*)malloc(sizeof(int)*str_len);
if (dp == NULL) return -1;

int i;
dp[0] = 1;
for (i = 1; i < str_len; i++) {
dp[i] = dp[i-1];
int value = (s[i-1] - '0') * 10 + (s[i] - '0');
if (value >= 10 && value <= 25) {
dp[i] += (i-2 >= 0 ? dp[i-2] : 1);
}
}
int ret = dp[str_len-1];
free(dp);
return ret;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int NumberOfPossibleStrings(String str){
if(str == null || str.length()==0) return 0;
if(str.length()==1)return 1;
if(str.length()==2)
if(str.charAt(0)<'3'&&str.charAt(0)>'0')return 2;
else return 1;

if(str.charAt(0)=='0'||str.charAt(0)>'2')
return NumberOfPossibleStrings(str.substring(1));
return NumberOfPossibleStrings(str.substring(1))+
NumberOfPossibleStrings(str.substring(2));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to srcnacks, but in c++

``````#include <string>
using namespace std;

int count_strings(string s)
{
if(s.length() <= 1)
return 1;

int count = count_strings(s.substr(1));

if(s[0] == '1' || (s[0] == '2' && s[1] <= '6'))
count += count_strings(s.substr(2));

return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

int num2letter( char num0, char num1)
{
assert( num0 >= '0'|| num0 <= '9' );
assert( num1 >= '0'|| num1 <= '9' );

if (0
|| num0 > '2'
|| (num0 == '2') && (num1 > '5')
) {
return 0;
}
return 1;
}

int search_str( const char * str, int start, int end, int num_found ) {
int num = num_found;
if (start < end) {
num++; // the very first one
num += num2letter(str[start], str[end]);
num += search_str(str, start+1, end, num);
} else if (start == end) {
num ++; // last one char
}

return num;
}

int main() {
const char num_str[] = "132493820173849029382910382";
int str_num = search_str( num_str, 0, sizeof(num_str) - 1 - 1, 0);
cout << "number of string is " << str_num << endl;
}

Comment hidden because of low score. Click to expand.
0

Sorry. The above code is wrong. The fixed one using simple DP is below:
{
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int num2letter( char num0, char num1)
{
assert( num0 >= '0'|| num0 <= '9' );
assert( num1 >= '0'|| num1 <= '9' );

if (0
|| num0 > '2'
|| (num0 == '2') && (num1 > '5')
) {
return 0;
}
return 1;
}

int search_str( const string &input) {
int num = 0;
vector<int> A(input.size(), 0);
A[0] = 1;
for(int i=0; i< input.size() - 1; i++) {
A[i+1] = A[i] + 1 + num2letter(input[i], input[i+1]);
}
return A.back();
}

int main() {
const string input = "132493820173849029382910382";
cout << "input:" << input << endl;
int str_num = search_str(input);
cout << "number of sub string is " << str_num << endl;

const string input1 = "1234";
cout << "input1:" << input1 << endl;
str_num = search_str(input1);
cout << "number of sub string is " << str_num << endl;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````# s non empty

def findComb(s):
# base cases:
if len(s) == 0:
return 1
elif len(s) == 1:
return 1
elif len(s) == 2:
if int(s) < 26:
return 2
else:
return 1

# recursive case, split the original string number to left and right
# total = findComb(left) * findComb(right) + \
#         findComb(left[:-1]) * findComb(right[1:])  //if <26

else:
mid = len(s) / 2
# print mid
left = s[:mid]
right = s[mid:]
easyComb = findComb(left) * findComb(right)
if int(s[mid-1:mid+1]) < 26:

Comment hidden because of low score. Click to expand.
0
of 0 vote

it should be simple to implement.
If english alphabets were from 1-99 then solution would have been (2n-1)
Since alphabets are till 25, we need to iterate through the list and figure out how many adjacent digits form a number more than 25 and exclude them from the ans.

``````number_of_string(int [] arr)
{
int exclude = 0;
for(int i=1;i<arr.length;i++)
{
if(arr[i-1]*10 + arr[i] > 25) exclude++;
}
return 2*arr.length -1 - exclude;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Only need to count numbers less than 26.
input: "132493820173849029382910382";

13, ...24, ... 20, ... 17, ... 10, ...
2^5 =32

output: 32

Comment hidden because of low score. Click to expand.
0

Hi, I also came up with this solution. And it works fine until the numbers overlap. Try for example 110511. Your approach will give 8, but the answer is 6. So we have to use DP in the end.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Only need to count numbers less or equal than 26

input: "132493820173849029382910382"

13, ... 24, ... 20, ...17,...13
2^5 = 32

output: 32

Comment hidden because of low score. Click to expand.
0

Hi, I also came up with this solution. And it works fine until the numbers overlap. Try for example 110511. Your approach will give 8, but the answer is 6. So we have to use DP in the end.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Main {

public static void printString(String prefix,String suffix, int len){
if(prefix.length()==len)
System.out.println(prefix);
else{
for(int i=0;i<suffix.length();i++){
char temp = (char)(Integer.parseInt(suffix.substring(0, 1)) + 65);
printString(prefix + String.valueOf(temp),suffix.substring(i+1, suffix.length()),len);
if(i<suffix.length()-1){
temp = (char)(Integer.parseInt(suffix.substring(0, 2)) + 65);
if(Integer.parseInt(suffix.substring(0, 2))<=25)
printString(prefix + String.valueOf(temp),suffix.substring(i+2, suffix.length()),len-1);
}

}
}

}

public static void main(String args[]){

String input = "1223" ;
String prefix="";
String suffix = "";
printString("",input,input.length());
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. assume the existence of a Hashtable<String, String> table that contains the mapping of a String number to String letter, e.g <"0", "A"> .... <"25", "Z">

2. assume the existence of a function:

``````private boolean isValid(String str) {
return table.containsKey(str);
}``````

3. The requested function:

``````public int CountCombo(String str) {

if(str.length <=0) return 0;

int ones = 0;
int twos = 0;

ones = (isValid(str.substring(0,1)))?1:0 + CountCombo(str.substring(1));

if(str.length>=2)
twos = (isValid(0,2))?1:0 + CountCombo(str.substring(2));

return ones + twos;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Java based on recursion:

``````public static int countStrings( char[] s, int n )
{
if ( n < 2 ) 	{
return 1;
}

int number = (s[n-1]-'0') + (s[n-2]-'0')*10;
if ( ( number >= 10 ) && ( number <= 25 ) )	{
return 1 + countStrings( s, n-1 ) + countStrings( s, n-2 );
}
else 	{
return 1 + countStrings( s, n-1 );
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int num_strings_o1space(const std::string& s)
{
int count_0 = 1;
int count_1 = 1;
int len = s.length();
for (auto i = 1; i < len; ++i)
{
int num = s[i-1] - '0';
num *= 10;
num += s[i] - '0';
if (s[i-1] != '0' && num < 26)
{
int count_new = count_0 + count_1;
count_0 = count_1;
count_1 = count_new;
}
else
{
count_0 = count_1;
}
}
return count_1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is a recursive solution in Java. I've also added cache to avoid calculating the same things more than once.

In each step, we try to take both 1 character and 2 characters (in case it's in the legal range).

The complexity without the cache is: 2^n (since the recurrence relation is T(n) = T(n-1) + T(n-2) in case the 2 chars forms a valid key).

``````public static int countValidWords(String input) {
if (input == null || input.isEmpty()) {
return 0;
}
Map<String, String> dict = new HashMap<>();
for (int i = 0; i < 26; i++) {
char c = (char) ('A' + i);
dict.put(i + "", c + "");
}

Map<String, Integer> cache = new HashMap<>();
return countValidWordsHelper(input, dict, "", cache);
}

private static int countValidWordsHelper(String input, Map<String, String> dict, String currentWord, Map<String, Integer> cache) {
// you can comment out the if below to get a print of all options (using cache
// doesn't print the parts that are already in the cache
if (cache.containsKey(input)) {
return cache.get(input);
}
if (input.length() == 0) {
System.out.println(currentWord);
return 1;
}
if (input.length() == 1) {
System.out.println(currentWord + ", " + dict.get(input));
return 1;
}
String currentPartCode = input.substring(0, 2);
String currentPartStr = dict.get(currentPartCode);

int validaWordsMinusChar = countValidWordsHelper(input.substring(1), dict, currentWord + ", " + dict.get(input.substring(0, 1)), cache);
cache.put(input.substring(1), validaWordsMinusChar);
int validWordsMinusTwoChars = 0;
if (currentPartStr != null) {
validWordsMinusTwoChars = countValidWordsHelper(input.substring(2), dict, currentWord + ", " + currentPartStr, cache);
cache.put(input.substring(2), validWordsMinusTwoChars);
}
return validaWordsMinusChar + validWordsMinusTwoChars;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.