Question

Microsoft | OA Coding Questions and Solutions | Set - 103 | 2022

Answer 1

Got this online assessment. I came up with a brute force solution where I constantly remove K characters and re-encode the whole string.
It doesn't seem to be efficient to me ... "it seems" that we should use some sort of "Sliding Window" to solve this but I must be missing something. Could someone give a clue?

 

 

public class Task2 {

    static int solution(String s, int k) {
        int kStart = 0, kEnd = k - 1, min = s.length();
        if (k == 0) return s.length();
        
        while (kEnd < s.length()) {
            String tmp = s.substring(0, kStart) + s.substring(kEnd + 1);
            System.out.println("original=" + s + " kStart=" + kStart + " kEnd=" + kEnd + " " + tmp +
                    "    " + encode(tmp));
            min = Math.min(encode(tmp).length(), min);
            kStart++;
            kEnd++;
        }

        return min;
    }

    static String encode(String s) {
        int count = 1;
        StringBuilder ss = new StringBuilder();
        for (int i = 1; i <= s.length(); i++) {
            if (i == s.length() || s.charAt(i) != s.charAt(i - 1)) {
                if (count > 1) {
                    ss.append(count);
                }
                ss.append(s.charAt(i - 1));
                count = 1;
            } else {
                count++;
            }
        }
        return ss.toString();
    }

    public static void main(String[] args) {
        //System.out.println(encode("ABCDDDEFG"));
        System.out.println("result=" + solution("ABBBCCDDCCC", 3));
        System.out.println();
        System.out.println("result=" + solution("AAAAAAAAAAABXXAAAAAAAAAA", 3));
        System.out.println();
        System.out.println("result=" + solution("ABCDDDEFG", 2));        
    }

}

Answer 2

As you mentioned, sliding window sticks out as the thing to do. A state during the iteration will look like [stuff on the left] [window of size k] [stuff on the right]. At any iteration, you will also have the length of the encoding. Initialization of this is easy: spend the O(N) time to compute the encoding length for S[k..n-1].

 

The effect of updating the sliding window (moving to the right by 1) is deleting a character on the right and adding one on the left. Based on the last character of [stuff on the left] and first character of [stuff on the right], you compute the new encoding length (taking into account merging left/right if necessary). I won't present the details, but you can imagine that such a computation is possible in O(1), since we're only making a very local change.

 

We can keep track of the minimal encoding length throughout this process and return the best answer.

 

Implementation note: I would probably represent the "stuff on the left/right" as list of (character, count) pairs. Also, to save space, I think it is only necessary to remember one thing (the last pair) on the left.

Answer 3

I came up with this O(N) time and O(N) space complexity solution. It works on the sample test cases. I haven't tested it thoroughly yet.

 

https://leetcode.com/playground/J5WRPjnR

 

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int findLen(int freq) {
        if (freq <= 1) {
            return freq;
        }
        
        int sol = 1;
        while (freq > 0) {
            sol++;
            freq /= 10;
        }
        return sol;
    }
    
  public:
    
    int shortestRunLengthEncoding(string s, int k) {
        int n = s.size();
        if (n == k) {
            return 0;
        }
        
        if (n < k) {
            return -1;
        }
        
        s = "#" + s + "$"; // To avoid dealing with edge cases.
        
        vector<int> leftLength(n + 2, 0), rightLength(n + 2, 0);
        
        // Precalculate the leftLength.
        int currLen = 0, currFreq = 0;
        for (int i = 1;i <= n;i++) {
            
            if (s[i] != s[i - 1]) {
                currLen += findLen(currFreq);
                currFreq = 1;
                leftLength[i] = currLen + findLen(currFreq);
                
            } else {
                currFreq++;
                leftLength[i] = currLen + findLen(currFreq);
            }
        }
        
        // Precalculate the rightLength.
        currLen = currFreq = 0;
        for (int i = n;i >= 1;i--) {
            
            if (s[i] != s[i + 1]) {
                currLen += findLen(currFreq);
                currFreq = 1;
                rightLength[i] = currLen + findLen(currFreq);
                
            } else {
                currFreq++;
                rightLength[i] = currLen + findLen(currFreq);
            }
        }
        
        vector<int> leftSameCharFreq(n + 2), rightSameCharFreq(n + 2);
        leftSameCharFreq[0] = 1;
        for (int i = 1;i <= n + 1;i++) {
            leftSameCharFreq[i] = (s[i] == s[i - 1]?leftSameCharFreq[i - 1] + 1:1);
        }
        rightSameCharFreq[n + 1] = 1;
        for (int i = n;i >= 0;i--) {
            rightSameCharFreq[i] = (s[i] == s[i + 1]?rightSameCharFreq[i + 1] + 1:1);
        }
        
        // Calculate the shortest encoding length.
        int minLength = INT_MAX / 2; // inf
        for (int i = 1;i <= n - k + 1;i++) {
            // If character before and after the window are same,
            // merge both of them.
            if (s[i - 1] == s[i + k]) {
                 int remStrLen = leftLength[i - 1] 
                     + rightLength[i + k] 
                     - findLen(leftSameCharFreq[i - 1]) 
                     - findLen(rightSameCharFreq[i + k]) 
                     + findLen(leftSameCharFreq[i - 1] + rightSameCharFreq[i + k]);
                minLength = min(minLength, remStrLen);
            } else {
                int remStrLen = leftLength[i - 1] + rightLength[i + k];
                minLength = min(minLength, remStrLen);
            }
        }
        
        return minLength;
    }
};

int main() {
    // Those who acknowledge themselves, and accept their true nature... THEY ARE THE STRONG ONES.
    
    // test cases:
    // "AAAAAAAAAAABXXAAAAAAAAAA" 3
    // "ABCDDDEFG" 2
    
    string str;
    int k;
    cin >> str >> k;
    Solution obj;
    cout << obj.shortestRunLengthEncoding(str, k);
    
    return 0;
}