Game of Strings

 Harsh and Akshara are playing the Game of Strings. This game is a simple one and is played as a team. Both the players of a team will be given a string respectively. At the end of this game, every team is required find out the length of the longest string S such that the strings given to each of the team members is a subsequence of S andS contains no vowels. Help Harsh and Akshara in finding out the required length. Input: Input consists of a single line containing two space separated strings. Output: The length of the longest string that satisfy the given conditions. Constraints: 1 <= length of string <=5000 Explanation The required string is "ng". if the constraint of the string S not containing vowels is removed, this becomes the classical Longest Common Subsequence (LCS) problem. For readers who are not familiar with LCS problem, they are encouraged to go through the following link which explains the problem as well to how to come up with the solution.http://en.wikipedia.org/wiki/Longest_common_subsequence_problem One can see that the LCS of the input two strings can never contain any vowels, hence, it is redundant to have vowels in the original string. Now, if we remove the vowels from the input strings, the problem is to find the length of the LCS of the edited strings. One can use the same approach described in the above wiki link to implement the solution. 

Test Case 1
 Input (stdin)
 abbs aabbss

 Expected Output
 3

 Test Case 2
 Input (stdin)
 mango mango

 Expected Output 3

Solution

1. #include<stdio.h>
2. #include<string.h>
3. long long a,b,i,j,array[5002][5002],x,y;
4. char name1[5002],name2[5002];
5. int main()
6. {
7. scanf("%s %s",name1,name2);
8. x=strlen(name1);
9. y=strlen(name2);
10. for(i=0;i<x;i++)
11. {
12. for(j=0;j<y;j++)
13. {
14. if(i==0)
15. {
16. if(j==0)
17. {
18. if(name1[i]==name2[j] && name2[j]!='a' && name2[j]!='e' && name2[j]!='i' && name2[j]!='o' && name2[j]!='u')
19. {
20. array[i][j]=1;
21. }
22. else
23. {
24. array[i][j]=0;
25. }
26. }
27. else if(j!=0)
28. {
29. if(name1[i]==name2[j] && name2[j]!='a' && name2[j]!='e' && name2[j]!='i' && name2[j]!='o' && name2[j]!='u')
30. {
31. array[i][j]=1;
32. }
33. else
34. {
35. array[i][j]=array[i][j-1];
36. }
37. }
38. }
39. else if(i!=0)
40. {
41. if(j==0)
42. {
43. if(name1[i]==name2[j] && name2[j]!='a' && name2[j]!='e' && name2[j]!='i' && name2[j]!='o' && name2[j]!='u')
44. {
45. array[i][j]=1;
46. }
47. else
48. {
49. array[i][j]=array[i-1][j];
50. }
51. }
52. else if(j!=0)
53. {
54. if(name1[i]==name2[j] && name2[j]!='a' && name2[j]!='e' && name2[j]!='i' && name2[j]!='o' && name2[j]!='u')
55. {
56. array[i][j]=array[i-1][j-1]+1;
57. }
58. else
59. {
60. a=array[i-1][j];
61. b=array[i][j-1];
62. if(a>=b)
63. {
64. array[i][j]=a;
65. }
66. else
67. {
68. array[i][j]=b;
69. }
70. }
71. }
72. }
73. }
74. }
75. printf("%lld\n",array[x-1][y-1]);
76. return 0;
77. }