Find the number of substrings of a string containing some anagram of another string as a subsequence

Question

We need to find the number of String substrings containing some anagram of another string as a subsequence.

Substrings are considered different only if the start or end positions are different.

String="aba"
anotherString="a"

Occurence of "a" in "aba" is as follows :

a     at index 0..0
ab    at index 0..1
aba   at index 0..2
ba    at index 1..2
a     at index 2..2

i.e total of 5 times...so o/p=5
(the start and end points here, are inclusive)

I thought this question is one of the uses of "the number of occurrences of a subsequence in a string" and "Find the smallest window in a string containing all the characters of another string".

But even after many changes in the combined code, I can’t come up with a solution. Inserting my code is useless as I know where I am going wrong. What I want to know is how we can effectively solve this without solving brute force.

The code:

public static void findLengthAndSequence(String str1,String str2){

    int begin=0,biginWith=0,endWith=0,count=0,minLen=Integer.MAX_VALUE,len=0;
    int l=0;

    int [] hasFound=new int[256];
    int [] toFound=new int[256];

    for(int i=0;i<str2.length();++i){           
        toFound[(int)str2.charAt(i)]++;
    }

    for(int end=0;end<str1.length();++end){
        if(toFound[(int)str1.charAt(end)]==0)
            continue;
        hasFound[(int)str1.charAt(end)]++;
        if(hasFound[(int)str1.charAt(end)]<=toFound[(int)str1.charAt(end)]){
            count++;
        }

        if(count==str2.length()){
            l++;        //add this to find number of such anagram in string
            System.out.println("l= "+l+" "+begin+" "+end); 
            while(toFound[(int)str1.charAt(begin)]==0 || hasFound[(int)str1.charAt(begin)]>toFound[(int)str1.charAt(begin)]  )
            {
                if(hasFound[(int)str1.charAt(begin)]>toFound[(int)str1.charAt(begin)]){
                    hasFound[(int)str1.charAt(begin)]-=1;                       
                }
                begin++;
            }//while
        len=end-begin+1;
        if(minLen>len){
            minLen=len;
            endWith=end;
            biginWith=begin;
        }
    }//if   
    }//end

    for(int i=biginWith;i<=endWith;++i){
        System.out.print(""+str1.charAt(i));
    }
}

= 3 . , , , .

e.g in "aba" my code checks for a,ab,aba.but once I reach the end it will not check   
ba,a .since we need to count this also as they are having different index values.

, , .

Answer 1

O(n + m) ( , ( n - ( )), m - ( )). , "good".

• count(x, y) y x. s t , count(s, c) >= count(t, c) c ( , ).

• firstRight(L) R, [L, R] (, R) . firstRight(L) <= firstRight(L + 1) L (- 1. count(x, y)).

• 1. , ​​ alphabetSize, i - i. 2. , .

• , :

  def getCharacterVector(string s):
      result = a vector filled with zeros
      for c in s
          result[c]++
      return result
  
  // Checks that all elements of the first vector
  // are greater than or equal to the corresponding
  // elements of the second vector
  def isGreaterOrEqual(first, second)
      for i = 0 ... length(first)
          if first[i] < second[i]
              return false
      return true
  
  def countSubstrings(string s, string t)
      vT = getCharacterVector(t)
      vS = a vector filled with zeros
      right = 0
      // computes firstRight(0)
      while (right < length(s) and not isGreaterOrEqual(vS, vT))
          vS[s[right]]++
          right++
      if not isGreaterOrEqual(vS, vT) // firstRight(0) is undefined
          return 0 // there are no such substrings
      res = length(s) - right + 1
      for left = 1 ... length(s) - 1
          vS[s[left - 1]]--
          // computes firstRight(left)
          while right < length(s) and vS[s[left - 1]] < vT[s[left - 1]]
              vS[s[right]]++
              right++
          if vS[s[left - 1]] < vT[s[left - 1]] // firstRight(left) is undefined
              break // we are done
           res += length(s) - right + 1
      return res
  

  , , , . - O(N * ALPHABET_SIZE + M) ( O(n + m), ), firstRight(0) , "" vS vT - O(n + m) .