# LensKart OA

This was one of the questions I got for Lenskart OA. Can someone help me understand how to solve this.
For the given sample input
a ={a}
b = {c,e}
h = {a, c}
So the combinations were
aa, bc, be, ha, hc

My apprach::

``````mod = pow(10, 9) + 7

from collections import defaultdict

count = 0

def helper(arr, sub, n, m):
global count
if len(sub) == n:
count = (count%mod) + 1
return
for i in range(0, len(arr)):
if not sub or arr[i] in m[sub[-1]]:
helper(arr, sub+[arr[i]], n, m)

def CountPossibleStrings (LanguageDevice, N):
# Write your code here
m = defaultdict(list)
rows = len(LanguageDevice)
cols = len(LanguageDevice[0])
res = 0
for r in range(rows):
for c in range(cols):
if LanguageDevice[r][c] == '1':
m[chr(ord('a')+r)].append(chr((ord('a')+c)))

for v in m.values():
helper(v, [], N-1, m)
return count

``````

I was not able to pass the test cases and I kep getting max recurssion depth error

``````static int MOD = (int)1e9 + 7;

public static void main(String[] args) {
char[][] chars = { { 'a', 'a' }, { 'b', 'c' }, { 'b', 'e' }, { 'h', 'a' }, { 'h', 'c'} };
int n = 2;
System.out.println(getNumOfStrs(chars, n));
}

private static int getNumOfStrs(char[][] chars, int n) {
Map<Character, Set<Character>> map = new HashMap<>();
for(char i = 'a'; i <= 'z';i++) {
map.put(i, new HashSet<>());
}
for(char[] cs : chars) {
}
int[][] dp = new int[n][26];
for(int i=0;i<n;i++) {
for(int j=0;j<dp[0].length;j++) {
if(i == 0) {
dp[i][j] = 1;
continue;
}
char cur = (char)(j + 'a');
for(char prev : map.getOrDefault(cur, new HashSet<>())) {
dp[i][j] = (dp[i][j] + dp[i-1][prev - 'a']) % MOD;
}
}
}
int res = 0;
for(int i=0;i<dp[0].length;i++)
res = (res + dp[n-1][i]);
return res;
}
``````