String Clockwise Shift Algorithm

Given strings a and b, and an integer k, return whether a can be converted to b by shifting some characters clockwise at most k times.

For example, “c” can be turned into “e” using 2 clockwise shifts.

Example 1
Input
a = “xyz”
b = “zzz”
k = 3
Output
true
Explanation
We can turn “x” into “z” using 2 clockwise shifts and then turn “y” into “z” using 1 clockwise shift, for a total of 3 shifts.

Example 2
Input
a = “aaa”
b = “aaa”
k = 0
Output
true

Compute the Minimal Steps to Clockwise Shift String

If strings are not equal length, it is impossible to convert one to another using the Clockwise Shift Algorithm. Otherwise, we need to accumulate the costs of conversion for each characters. We can easily do this by subtracting the ASCII code differences of corresponding letter.

C++ Clockwise Shift Cost Computation:

1
2
3
4
5
6
7
8

bool stringClockwiseShiftCost(string a, string b, int k) {
    if (a.size() != b.size()) return false;
    for (int i = 0; i < a.size(); ++ i) {
        k -= ((b[i] - a[i] + 26) % 26);
        if (k < 0) return false;
    }
    return true;
}

bool stringClockwiseShiftCost(string a, string b, int k) {
    if (a.size() != b.size()) return false;
    for (int i = 0; i < a.size(); ++ i) {
        k -= ((b[i] - a[i] + 26) % 26);
        if (k < 0) return false;
    }
    return true;
}

Python Implementation of the same String Shifting Algorithm:

1
2
3
4
5
6
7
8
9

class Solution:
    def stringClockwiseShiftCost(self, a, b, k):
        if len(a) != len(b):
            return False
        for i in range(len(a)):
            k -= (ord(b[i]) - ord(a[i]) + 26) % 26
            if k < 0:
                return False
        return True

class Solution:
    def stringClockwiseShiftCost(self, a, b, k):
        if len(a) != len(b):
            return False
        for i in range(len(a)):
            k -= (ord(b[i]) - ord(a[i]) + 26) % 26
            if k < 0:
                return False
        return True

Both implementations are O(N) time and O(1) space where N is the size of the string a/b.

–EOF (The Ultimate Computing & Technology Blog)