fork download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		Solution s  =  new Solution();
  13. 		Scanner sc =  new Scanner(System.in);
  14. 		//String a  = sc.next();
  15. 		//String b  = sc.next();
  16. 		//int ans  = s.find(a , b);	// your code goes here
  17. 		sc.close();
  18. 	}
  19. }
  20.  
  21. class Solution{
  22. 	//NUMBER OF subsequences in a that rae strinctLY greater thaN teh suBsequences in b
  23. 	public static int find(String A , String B){
  24. 		int n = A.length();
  25. 		int  m  = B.length();
  26. 		char[] a = A.toCharArray();
  27. 		char[] b =  B.toCharArray();
  28. 		//comment on the dp state - > 
  29. 		/*
  30. 		dp[i][j] = tells the number of subsequences from i-n-1 ..... that are strictly greater than j-------m-1
  31. 		*/
  32. 		int[][] dp = new int[n][m];
  33.  
  34. 		//filling the bottom row first 
  35. 		if(b[m-1] > a[n-1]){
  36. 			dp[n-1][m-1] = 1;
  37. 		}
  38. 		for(int i  = m-2 ; i>= 0 ; i--){
  39.  
  40. 			char froma = a[n-1];
  41. 			char fromb = b[i];
  42.  
  43. 			if(froma > fromb){
  44. 				//then teh answer ahead + thischaracter*allsubsequences ahread possible;
  45. 				dp[n-1][i] = dp[n-1][i+1]  + (int)(1*Math.pow(2 , m-i-1) - 1); // that is  the second figure is from fixing this character in B and all other subsequnces combined with this char
  46. 			}else if(froma < fromb){
  47.  
  48. 				dp[n-1][i] = dp[n-1][i+1];
  49. 			}else{
  50. 				//when both the current character are equal;
  51. 				dp[n-1][i] = dp[n-1][i+1]; //because current As substring is just tshe last character  .. if that is equal to the current character of B
  52. 				//then it menas that  we will consider the case of the subseq formed by the string ahead in B .. and ... 
  53. 				//no ostring made up of this character in B will be lesser than A as lexicograhically it will be longer
  54. 			}
  55. 		}
  56.  
  57. 		//now filling the last column   ... means that we will be comparing the last character of B with all sbstring subsequences from last to first in A
  58. 		for(int i  = n-2 ; i>=0 ; i--){
  59. 			char fromb = b[m-1];
  60. 			char froma = a[i];
  61. 			if(froma > fromb){                         //basically all subsequesces in the string ahead except the null one
  62. 				dp[i][m-1] = dp[i+1][m-1] + (int)(1*Math.pow(2 , n-i-1) - 1);
  63.  
  64. 			}else if(froma < fromb){
  65. 				dp[i][m-1] = dp[i+1][m-1];
  66. 			}else{
  67. 				//example A => abcd
  68. 				//B => bcbb
  69. 				//last character of B = b
  70. 				//let current substring of A  = bcd
  71. 				//as b == b it means we will have to take all the cases of the prev substring that is cd + we will take the case where 'b,  from A is compusalry
  72. 				//and we want to take all the combinations of the ssubsequnces fromes from the substring ahead ... as As subsequence length  after 
  73. 				//compulsarily taking  'b,  from bcd we are left with cd .. and we will take all non null subsequences
  74. 				dp[i][m-1] = dp[i+1][m-1] + (int)(1*Math.pow(2 , n-i) -1);
  75.  
  76. 			}
  77. 		}
  78.  
  79.  
  80. 		//now for all the remianing 
  81. 		for(int i  = n-2  ; i>= 0 ; i--){
  82. 			for(int j = m-2 ; j>=0 ; j--){
  83. 				char froma = a[i];
  84. 				char fromb = b[j];
  85. 				if(froma > fromb){			//fixing the current character at i in j 
  86. 					dp[i][j] = dp[i+1][j] + (int)(1*Math.pow(2 , n-1 - i));
  87. 				}else if(froma < fromb){
  88. 					dp[i][j] = dp[i+1][j] ;
  89. 				}else{
  90. 					dp[i][j] = dp[i+1][j] + dp[i+1][j+1];
  91. 				}
  92.  
  93. 			}
  94. 		}
  95.  
  96. 		return dp[0][0];
  97.  
  98. 	}
  99.  
  100.  
  101. }
Success #stdin #stdout 0.14s 54624KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Bmx5nf
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!