A Special Keyboard Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/228d0aa9f26db93ee5b2cb3583dbd4b197447e16/1

(It is also the problem of the day for 23-05-2022)

Solution:

Approach 1: Using Map

class Solution {

    static int findTime(String s1 , String s2) {

        LinkedHashMap<Character,Integer>map=new LinkedHashMap<Character,Integer>();

        

        for(int i=0;i<s1.length();i++){

            map.put(s1.charAt(i),i);

        }

       // System.out.println(map);

        

        int sum=0;

        

        int point=0;

        

        for(int i=0;i<s2.length();i++){

            char a=s2.charAt(i);

            int val=map.get(a);

            sum=sum+Math.abs(point-val);

            point=val;

        }

        return sum;

        

    }

};

Time Complexity: O(S1)[GFG Time:0.49/6.28]

Space Complexity: O(1)[Strings are given]

Auxiliary Space: O(S1)[Map is used]

Total Test Cases:10203

Approach Used:

1. Here we will store all the characters with their index on the map.

2. Now traversing the second string we will take out the value of each character(key in the map) and do two operations:

    1. Find differences with the pointer variable.

    2. Add the difference in the sum variable.

Here the point variable will be the index of character. As we will have to move to different characters so for that point will store the previous pointing character and the difference will find out the difference between the current character and the previous character.

This difference means the displacement which will keep on adding in the sum variable and return it later.

ex 

initally point =0 

String s1="abcdefghijklmnopqrstuvwxyz"

String s2="cgb"

first character: c

point=0;[Previous]

val=2(index of c)[Current]

sum=sum+Math.abs(point-val)

sum=0+(2-0)=2

point=val=2[updtaed value of point]

Second character:g

point=2

val=6(inde of g)[Curent]

sum=sum+Math.abs(point-val)

sum=2+(6-2)=6

point=val=6[updtaed value of point]

Third character:b

point=1

val=1(inde of b)[Curent]

sum=sum+Math.abs(point-val)

sum=6+(6-1)=11

point=val=1[updtaed value of point]

The final value of the sum is 11

return 11

=========================================================================

Approach 2: Without Using Map

 int point=0;

        int sum=0;

        for(int i=0;i<s2.length();i++){

            int val=s1.indexOf(s2.charAt(i));

            sum=sum+Math.abs(val-point);

            point=val;

        }

        return sum;

Time Complexity: O(S2)[GFG Time:0.34/6.28]

Space Complexity: O(1)

Auxiliary Space: O(1)

Total Test Cases:10203

Approach Used:

1. Here we will add on the index of every character by taking its difference with the point variable.

It is also based on the previous approach but the difference is 

In the previous approach, we used the map for finding out the index of characters while here we are using the inbuilt function indexOf() to find out the index.

The rest is the same.

Why we are using the indexOf() function?

It is so because we know that the string contains only unique characters so we can use the indexOf() method, while if we had duplicates we need to think according to that.

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure😊.