Find time taken to string S2

Question

Imagine you have a special keyboard with all keys in a single row. The layout of characters on a keyboard is denoted by a string S1 of length 26. S1 is indexed from 0 to 25. Initially the index is at 0. To type a character we need to move the index of desired character. The time taken to move the index from i to j is |j-i| where || is absolute Value.

Given a string s1 and s2, describe the time taken to type string s2.

Given two string S1 and S2 where S1 = abcdeghijklmnopqrstuvwxyz

s2 = cba

and starting with index 0 ('A') find the time taken to type cba.

index of c = 2
count = 2 - 0
count = 2 + 1 (c to b )
count = 2 + 1(c to b) + 1 (b to a)
count returned should be 4.

I am sure this is easy to do in quadratic by running two loops but that is not an efficient solution. Any ideas how I can improve this?

Answer 1

Big Edit

Actually, by definition, the fact that S1 is a fixed length and does not depend on the input S2 means that @Amiy's answer is correct. Because indexOf runs only on S1, it will take at most a constant 26 steps. O(26n) = O(n). My answer is just a lower constant, running in 1n to 2n depending on the variation.

---

Another Edit

For the general case, where S1 is also a variable input and we can make no assumptions about it, see @user000001's hashing solution in O(nlogm).

---

Original Answers

If you rely on the fact that S1 is sorted and that each character is a value 1 off from its neighbours, you could just calculate the difference between the characters in S2 and sum it up

For example:
S2 = cba

Prepend a to S2 to get the starting value:
S2 = acba

For each character c1 and its right-neighbour c2 in S2,
distance += |c1 - c2|

---

If you don't rely on the fact that S1 is sorted (which is probably what you're looking for), you could index the values of S1 into an array and apply a similar algorithm as above:

For example:

S1 = "qwertyuiopasdfghjklzxcvbnm"
arr = array of size 26
let i = 0
for each character c in S1:
    arr[c - 'a'] = i++

Then, adapt the algorithm:

S2 = "cba"
let distance = 0
for each character c1 and its right-neighbour c2 in S2:
    distance += |arr[c1 - 'a'] - arr[c2 - 'a']|

---

Both algorithms solve the problem in O(n), whereas the first one uses O(1) space and the second uses O(n) space.

Answer 2

One way to reduce the complexity from O(N^2) to O(Nlog(N), would be to create a HashMap out of the String.

Something like this:

String s1 = "abcdeghijklmnopqrstuvwxyz";
String s2 = "cba";

Map<Byte, Integer> map = new HashMap<>();

int i = 0;
for (Byte b: s1.getBytes()) {
    map.put(b, i++);
}

int result = 0;
int previndex = 0;
for (Byte b: s2.getBytes()) {
    int currentindex = map.get(b);
    result += (int) Math.abs(currentindex - previndex);
    previndex = currentindex;
}

System.out.println("resutlt= " + result);

Answer 3

This one is more simpler to understand:

String s1 = "abcdefghijklmnopqrstuvwxyz";
String s2 = "cba";
int jumps = 0;

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

        if(i==0){
            jumps += s1.indexOf(s2.charAt(i));
        }else{
            jumps += Math.abs(s1.indexOf(s2.charAt(i)) - s1.indexOf(s2.charAt(i-1)));
        }
}
System.out.println("Total Jumps: "+jumps);

Here, it looks for each character of s2 in s1 with a loop. First time the if block will run and then else for the remaining characters. For every character in s2, it will keep adding the jumps/hops/time-taken to the total and will return you after the loop is done.

Also, it counts the jumps by subtracting the char-position of where we are from the char-position of where we were. In simple terms, since it starts with position 0, you can count like this: [(C-0)+(B-C)+(B-A)].

Answer 4

Here is the algorithm in Java:

String s1 = "abcdefghijklmnopqrstuvwxyz";
String s2 = "cba";

int pos = 0;
int time = 0;

for (int ind = 0;ind < s2.length(); ind++) {
    char cur_char = s2.charAt(ind);
    index = s1.indexOf(cur_char);
    time += Math.abs(index - pos);
    pos = index;
}

System.out.println("Time taken: " + time);

For above values output is: Time taken: 4

Edit:
Time complexity of this algorithm is O(n)
Since length of s1 is constant, let k.
And length of string s2 ia variable, let n.
Time complexity: O(nk) = O(n) [Since k is a constant value]