How can I optimize this algorithm? Working with chars

Question

Task: We are given two strings of the same length, m and n. We want to modify m into n. We can perform two operations;

We can take a contiguous segment of the current string and either shift each letter in the segment forward in the alphabet once, or backward in the alphabet.

We want to complete this in the minimum number of steps, the goal is an O (n) algorithm.

So here's my first stab at it; obviously not even close to being as optimized as it could be, but I'm kind of lost as to how to optimize it. I'm not sure how to determine what segment of letters would be best to take. My implementation just goes through one letter at a time currently.

public static void shift(String m, String n) {
    char mChar[] = m.toCharArray();
    char nChar[] = n.toCharArray();

    int count = 0;
    for (int i = 0; i < m.length(); i++){
        while (mChar[i] != nChar[i]){
            if (mChar[i] - nChar[i] < 0){
                //System.out.println("SHIFT FORWARD");
                mChar[i]++;
                count++;
            }
            else{
                //System.out.println("SHIFT BACKWARD");
                mChar[i]--;
                count++;
            }
            System.out.println(mChar[i]);
        }
    }
    System.out.println(mChar);
    System.out.println(count);
}

Also what would be the time complexity of this algorithm as is? The For loop makes it at the minimum O (n), and the while loop could run 25 times in the worst case (if we had 'y' and wanted 'a'). Am I right in this thinking?

Answer 1

Although @Andreas 's answer is viable, it's not O(N). You want to think about the worst case when you then in the minute details it'll be..

How to implement Andreas's answer

you need to know the size of the gaps, so not where it changes indices, but the blocks themselves. Have 2 temp variables -> int startIndex, endIndex...

startIndex = 0, endIndex = -1 at first, and then when you see the sign change, change endIndex = i, record that block length i-startIndex in your blockSize[] append...

then when you see another change, startIndex = endIndex, endIndex = i, record i-startIndex in your blockSize[] append...

When you're done with that, the answer-producing block of code goes like this...

Thinking...

"I need to increment... the last 4 blocks.. let's go through our array which might be size N, let's see.. okay the last 4 is biggest block, now let's go increment the last 4"

Now why is that bad?

You need to go through that size N array everytime you go through the incrementing process, which is why it leads to N^2, do you see what I mean? for big Oh, you always need to think of the literal worst case, which in yours is

[1, -1, 1, -1, 1, -1]

what will you do then? You'll create a gap size array of

[1,1,1,1,1,1]

and then you'll have to go through those gap size array N times to find thebiggest size which is actually any of them so then you'll go through N times to find the biggest size through an N sized, alternating array hence N^2.

Here's another method, but I'm not completely sure if it'll be O(N) or O(N*k), where k is factoring in the # of processes required to shift one letter by one(because you specified that).

[1, -1, 1, -1, 1, -1]
remove 1 from everything
[0, -2, 0, -2, 0, -2]
next time you remove 2 from everything EXCLUDING the 0's
(keep track of the 0's in another array as a flag)
[0,0,0,0,0,0] is your 2nd run through of the array
so 2 shifting operations as opposed to 36

Of course, doing it my method has its worst case too, shown below:

[1, 4, 12, -3, -2, 3] let's say... 
1st. [0,3,11,-4,-3,2]
2nd. [0,0,8,-7,-6,-1]
3rd. [0,0,0,-15,-14,-9]

This will lead to a total of 6 operations, but the indices to increment has almost quadrupled in the last 3. I don't know if you're going straight from a -> z, or a->b->c... If it's the former, then I don't think the avalanche effect will be significant.

I can't think of any O(N) operations other than this, which require k to be constant.

When someone answers a question regarding big O computational speed, you should always think of this phrase:

A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates. - Wikipedia

Although @Andrea's answer is elegant and on average probably performs well, it's not O(N) because the upper bound on the growth rate can be much higher than you expected.

Answer 2

Since you're supposed to learn how to program, I won't give you the code, but I can help you with the right algorithm in this case.

I'll do it by example:

shift( "AAAAZZZZ", "BCDBZYYX" )

The goal here is to minimize the number of shift operations, so you need to optimize the block size being shifted.

First, identify the number of shifts needed for each character:

A  A  A  A  Z  Z  Z  Z
B  C  D  B  Z  Y  Y  X
+1 +2 +3 +1 0  -1 -1 -2

Starting at the first position, if the shift is positive, find the largest consecutive block of positive shifts. If negative, find block of negative shifts. Apply shift. Repeat until zero, and go to next character.

1: Index 0 to 3, shift up:

B  B  B  B  Z  Z  Z  Z
0  +1 +2 0  0  -1 -1 -2

2: Index 1 to 2, shift up:

B  C  C  B  Z  Z  Z  Z
0  0  +1 0  0  -1 -1 -2

3: Index 2, shift up:

B  C  D  B  Z  Z  Z  Z
0  0  0  0  0  -1 -1 -2

4: Index 5 to 7, shift down:

B  C  D  B  Z  Y  Y  Y
0  0  0  0  0  0  0  -1

5: Index 7, shift down:

B  C  D  B  Z  Y  Y  X
0  0  0  0  0  0  0  0

Done in 5 shift operations.

Update

Optimization: Program doesn't need to "identify the number of shifts" up front, or at all. That was mostly done to help illustrate the algorithm.