fork download
copy 
  1. import java.util.*;
  2. class Subsequence2Pointer {
  3.  
  4.     public static int numOfGoodIndices(String a, String b) {
  5.  
  6.         int n = a.length();
  7.         int m = b.length();
  8.  
  9.         // If b has only one character,
  10.         // removing it leaves empty string,
  11.         // which is always a subsequence.
  12.         if (m == 1) {
  13.             return 1;
  14.         }
  15.  
  16.         int[] left = new int[m];
  17.         int[] right = new int[m];
  18.  
  19.         Arrays.fill(left, -1);
  20.         Arrays.fill(right, -1);
  21.  
  22.         // Build left[]
  23.         // left[i] = earliest position in a
  24.         // where b[0...i] can be matched.
  25.         int j = 0;
  26.  
  27.         for (int i = 0; i < n && j < m; i++) {
  28.             if (a.charAt(i) == b.charAt(j)) {
  29.                 left[j] = i;
  30.                 j++;
  31.             }
  32.         }
  33.  
  34.         // Build right[]
  35.         // right[i] = latest position in a
  36.         // where b[i...m-1] can be matched.
  37.         j = m - 1;
  38.  
  39.         for (int i = n - 1; i >= 0 && j >= 0; i--) {
  40.             if (a.charAt(i) == b.charAt(j)) {
  41.                 right[j] = i;
  42.                 j--;
  43.             }
  44.         }
  45.  
  46.         // if an index is supposed to be good then left[i-1] < right[i+1]
  47.         // meaning index i-1 in b was found at left[i-1] and occurs before right[i+1] occurance 
  48.         // 
  49.  
  50.         int good = 0;
  51.  
  52.         for (int i = 0; i < m; i++) {
  53.         	int l = (i == 0) ? -1 : left[i - 1];
  54.         	int r = (i == m - 1) ? n : right[i + 1];
  55.         	boolean prefixOk = (i == 0) || (l != -1);
  56.         	boolean suffixOk = (i == m - 1) || (r != -1);
  57.         	if (prefixOk && suffixOk && l < r) {
  58.         		good++;
  59.         	}
  60.         }
  61.  
  62.         return good;
  63.     }
  64.  
  65.     public static void main(String[] args) {
  66.         //"If b itself is already a subsequence of a, then removing any character from b should still give a subsequence."
  67.         // if not subsequence then IFF we have one char somewhere that needs to be removed then thats the ans.. 
  68.         // so either ans is 1 or length of string or 0 if not possible at all
  69.         String a = "abxcdyef";
  70.         String b = "abcde";
  71.  
  72.         System.out.println(numOfGoodIndices(a, b));
  73.         System.out.println(numOfGoodIndices("abc", "xy"));
  74.         System.out.println(numOfGoodIndices("abcd", "ayd"));
  75.     }
  76. }
Success #stdin #stdout 0.08s 54552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
0
1
https://ideone.com/wkYAQP
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!