Substring Of Size Three with Distinct Characters LeetCode

 Problem Link:

https://leetcode.com/problems/substrings-of-size-three-with-distinct-characters/

Solution:

class Solution {

    public int countGoodSubstrings(String s) {

            ArrayDeque<Character>aa=new ArrayDeque<Character>();

            if(s.length()<3){

                return 0;

            }

        else{

            int count=0;

            aa.addLast(s.charAt(0));

             aa.addLast(s.charAt(01));

             aa.addLast(s.charAt(02));

            if(s.charAt(0)!=s.charAt(1) && s.charAt(1)!=s.charAt(2) && s.charAt(0)!=s.charAt(2)){

                count++;

            }

            //System.out.println(aa);

            boolean flag=false;

            for(int i=3;i<s.length();i++){

                aa.removeFirst();

                //System.out.println(aa);

                aa.addLast(s.charAt(i));

                char a=aa.removeLast();

                char b=aa.removeLast();

                char c=aa.removeLast();

                 if(a!=b && b!=c && a!=c){

                    /* System.out.println(a);

                           System.out.println(b);      System.out.println(c);*/

                    count++;

                }

                aa.addFirst(a);

                aa.addFirst(b);

                aa.addFirst(c);

               // System.out.println(aa);

                

            }

              

            return count;

                

                

        }

    }

}

TIME:O(String Length)[One Time Iteration][LeetCode Time:2ms faster than 48.93%]

SPACE:O(3)[At one instant ArrayDeque Will Have Only 3 values. Not more than 3 or less than 3][LeetCode Memory:36.6 MB less than 99.81%]

APPROACH:

1. Store the first three values in ArrayDeque aa. 

2. See if the three values are all distinct, if yes then increment the counter variable count. 

3. Start traversing array from index value 3 to rest of length.

4. Now we need to add character at last but for adding we need to remove one character from start otherwise the size of the array deque will increase. So for that first, we will pop out starting character using the aa.removeFirst() function.

5. After removing the size of aa will be 2 and now we will add the incoming character at the end using aa.addLast(string.charAt(i)).

6. Now we will pop out all the elements and store them in three different characters variables a,b, and c.

7. If a,b, and c are different then count++ else no increment in the count.

8. Now we will add these values a,b and c back to aa but now from first in manner as to preserve their position as it was before removal.

9. Return count.

[The basic idea to remove aa is to match all three characters are distinct. We can also apply the same approach but not by adding the character first in aa instead of using the incoming character s.charAt(i) for comparison with a and b when aa size is 2. And later we can add back in aa. This will reduce time.]

"Thanks for Reading.😊"

"Share Further To Increase Knowledge Treasure.😇"