No. 49 - Longest Substring without Duplication

Problem: Given a string, please get the length of the longest substring which does not have duplicated characters. Supposing all characters in the string are in the range from ‘a’ to ‘z’.

Analysis: It’s not difficult to get all substrings of a string, and to check whether a substring has duplicated characters. The only concern about this brute-force strategy is performance. A string with n characters has O(n²) substrings, and it costs O(n) time to check whether a substring has duplication. Therefore, the overall cost is O(n³).

We may improve the efficiency with dynamic programming. Let’s denote the length of longest substring ending with the i^th character by L(i).

We scan the string one character after another. When the i^th character is scanned, L(i-1) is already know. If the i^th character has not appeared before, L(i) should be L(i-1)+1. It’s more complex when the i^th character is duplicated. Firstly we get the distance between the i^th character and its previous occurrence. If the distance is greater than L(i-1), the character is not in longest substring without duplication ending with the (i-1)^th character, so L(i) should also be L(i-1)+1. If the distance is less than L(i-1), L(i) is the distance, and it means between the two occurrence of the i^th character there are no other duplicated characters.

This solution can be implemented in Java as the following code:

public static int longestSubstringWithoutDuplication(String str) {

    int curLength = 0;

    int maxLength = 0;

    int position[] = new int[26];

    for(int i = 0; i < 26; ++i) {

        position[i] = -1;

    }

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

        int prevIndex = position[str.charAt(i) - 'a'];

        if(prevIndex < 0 || i - prevIndex > curLength) {

            ++curLength;

        }

        else {

            if(curLength > maxLength) {

                maxLength = curLength;

            }

            curLength = i - prevIndex;

        }

        position[str.charAt(i) - 'a'] = i;

    }

    if(curLength > maxLength) {

        maxLength = curLength;

    }

    return maxLength;

}

L(i) is implemented as curLength in the code above. An integer array is used to store the positions of each character.

Code with unit tests is shared at http://ideone.com/CmY3xN.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

No. 48 - Least Number after Deleting Digits

Problem: Please get the least number after deleting k digits from the input number. For example, if the input number is 24635, the least number is 23 after deleting 3 digits.

Analysis: Let’s delete a digit from the number at each step. What’s the first digit to be deleted from the number 24635, in order to get the least number with the remaining digits? We may list all the remaining numbers after deleting a digit, in the following table:

Deleted Digit	Remaining Number
2	4635
4	2635
6	2435
3	2465
5	2463

The number 2435 is the least one in all remaining numbers, by deleting the digit 6. Notice that the digit 6 is the first digit in the number 24635 which is greater than the next digit.

Let’s delete another digit from the number 2435, the remaining least number after the first step. We may summarize the remaining numbers after delete every digit from it in the following table:

Deleted Digit	Remaining Number
2	435
4	235
3	245
5	243

The number 235 is the least one in all remaining numbers, by deleting the digit 4. Notice that the digit 4 is the first digit in the number 2435 which is greater than the next digit.

The remaining three digits in the number 235 are increasingly sorted. What is the next digit to be deleted to get the least remaining number? Again, we may list the remaining numbers after deleting each digit in a table:

Deleted Digit	Remaining Number
2	35
3	25
5	23

The number 23 is the least one in all remaining numbers, by deleting the last digit 5.

If we are going to deleting more digits from a number whose digits are increasingly sorted to get the least number, the last digit is deleted at each step.

Now we get the rules to delete digits to get the least remaining number: If there are digits who are greater than the next one, delete the first digit. If all digits in the number are increasingly sorted, delete the last digit gets deleted. The process repeats until the required k digits are deleted.

The code can be implemented in Java as the following:

public static String getLeastNumberDeletingDigits_1(String number, int k) {

    String leastNumber = number;

    while(k > 0 && leastNumber.length() > 0) {

        int firstDecreasingDigit = getFirstDecreasing(leastNumber);

        if(firstDecreasingDigit >= 0) {

            leastNumber = removeDigit(leastNumber, firstDecreasingDigit);

        }

        else {

            leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);

        }

        --k;

    }

    return leastNumber;

}

private static int getFirstDecreasing(String number) {

    for(int i = 0; i < number.length() - 1; ++i) {

        int curDigit = number.charAt(i) - '0';

        int nextDigit = number.charAt(i + 1) - '0';

        if(curDigit > nextDigit) {

            return i;

        }

    }

    return -1;

}

private static String removeDigit(String number, int digitIndex) {

    String result = "";

    if(digitIndex > 0) {

        result = number.substring(0, digitIndex);

    }

    if(digitIndex < number.length() - 1) {

        result += number.substring(digitIndex + 1);

    }

    return result;

}

Optimization: Save the start index for the next round of search for the first decreasing digit

In the method getFirstDecreasing above to get the first digit which is greater than the next one, we always start from the first digit. Is it necessary to start over in every round of search?

The answer is no. If the i^th digit is the first digit which is greater than the next one, all digits before the i^th digit are increasingly sorted. The (i-1)^th digit might be less than the (i+1)^th digit, the next digit of the (i-1)^th digit after the i^th digit is deleted. Therefore, it is safe to start from the (i-1)^th digit in the next round of search.

With this optimization strategy, the efficiency gets improved from O(n*k) to O(n), if the length of the input number has n digits and k digits are deleted.

The optimized solution can be implemented as:

class DecreasingResult {

    public int firstDecreasing;

    public int nextStart;

}

public static String getLeastNumberDeletingDigits_2(String number, int k) {

    String leastNumber = number;

    int start = 0;

    while(k > 0 && leastNumber.length() > 0) {

        DecreasingResult result = getNextDecreasing(leastNumber, start);

        if(result.firstDecreasing >= 0) {

            leastNumber = removeDigit(leastNumber, result.firstDecreasing);

        }

        else {

            leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);

        }

        start = result.nextStart;

        --k;

    }

    return leastNumber;

}

private static DecreasingResult getNextDecreasing(String number, int start) {

    int firstDecreasing = -1;

    int nextStart;

    for(int i = start; i < number.length() - 1; ++i) {

        int curDigit = number.charAt(i) - '0';

        int nextDigit = number.charAt(i + 1) - '0';

        if(curDigit > nextDigit) {

            firstDecreasing = i;

            break;

        }

    }

    if(firstDecreasing == 0) {

        nextStart = 0;

    }

    else if (firstDecreasing > 0) {

        nextStart = firstDecreasing - 1;

    }

    else {

        nextStart = number.length();

    }

    DecreasingResult result = new DecreasingResult();

    result.firstDecreasing = firstDecreasing;

    result.nextStart = nextStart;

    return result;

}

Code with unit tests is shared at http://ideone.com/0Mdfcf.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

No. 43 - Minimal Number of Palindromes on a String

Problem: A string can be partitioned into some substrings, such that each substring is a palindrome. For example, there are a few strategies to split the string “abbab” into palindrome substrings, such as: “abba”|”b”, “a”|”b”|”bab” and “a”|”bb”|”a”|”b”.

Given a string str, please get the minimal numbers of splits to partition it into palindromes. The minimal number of splits to partition the string “abbab” into a set of palindromes is 1.

Analysis: This is a typical problem which can be solved by dynamic programming. We have two strategies to analyze and solve this problem

Solution 1: Split at any space between two characters

Given a substring of str, starting from the index i and ending at the index j (denoted as str[i:j]), we define a function f(i, j) to denote the minimal number of splits to partition the substring str[i:j] into a set of palindromes. If the substring is a palindrome itself, we don’t have to split so f(i, j) is 0. If the substring is not a palindrome, the substring is split between two characters k and k+1. f(i, j)= f(i, k)+ f(k+1, j)+1 under such conditions. Therefore, f(i, j) can be defined with the following equation:

The value of f(0, n-1) is the value of the minimal number of splits to partition str into palindromes, if n is the length of str.

If the equation is calculated recursively, its complexity grows exponentially with the length n. A better choice is to calculate in bottom-up order with a 2D matrix with size n×n. The following C++ code implements this solution:

int minSplit_1(const string& str)

{

    int length = str.size();

    int* split = new int[length * length];

   

    for(int i = 0; i < length; ++i)

        split[i * length + i] = 0;

    for(int i = 1; i < length; ++i)

    {

        for(int j = length - i; j > 0; --j)

        {

            int row = length - i - j;

            int col = row + i;

            if(isPalindrome(str, row, col))

            {

                split[row * length + col] = 0;

            }

            else

            {

                int min = 0x7FFFFFFF;

                for(int k = row; k < col; ++k)

                {

                    int temp1 = split[row * length + k];

                    int temp2 = split[(k + 1) * length + col];

                    if(min > temp1 + temp2 + 1)

                        min = temp1 + temp2 + 1;

                }

                split[row * length + col] = min;

            }

        }

    }

    int minSplit = split[length - 1];

    delete[] split;

    return minSplit;

}

Solution 2: Split only before a palindrome

We split the string str with another strategy. Given a substring ending at the index i, str[0, i], we do not have to split if the substring is a palindrome itself. Otherwise it is split between two characters at index j and j+1 only if the substring str[j+1,i] is a palindrome. Therefore, an equation f(i) can be defined as the following:

The value of f(n-1) is the value of the minimal number of splits to partition str into palindromes, if n is the length of str.

We could utilize a 1D array to solve this equation in bottom-up order, as listed in the following code:

int minSplit_2(const string& str)

{

    int length = str.size();

    int* split = new int[length];

    for(int i = 0; i < length; ++i)

        split[i] = i;

    for(int i = 1; i < length; ++i)

    {

        if(isPalindrome(str, 0, i))

        {

            split[i] = 0;

            continue;

        }

        for(int j = 0; j < i; ++j)

        {

            if(isPalindrome(str, j + 1, i) && split[i] > split[j] + 1)

                split[i] = split[j] + 1;

        }

    }

    int minSplit = split[length - 1];

    delete[] split;

    return minSplit;

}

Optimization to verify palindromes:

Usually it costs O(n) time to check whether a string with length n is a palindrome, and the typical implementation looks like the following code:

bool isPalindrome(const string& str, int begin, int end)

{

    for(int i = begin; i < end - (i - begin); ++i)

    {

        if(str[i] != str[end - (i - begin)])

            return false;

    }

    return true;

}

Both solutions above cost O(n³) time. The first solution contains three nesting for-loops. The function isPalindrome is inside two nesting for-loops.

If we could reduce the cost of isPalindrome to O(1), the time complexity of the second solution would be O(n²).

Notice that the substring str[i,j] is a palindrome only if the characters at index i and j, and str[i+1,j-1] is also a palindrome. We could build a 2D table accordingly to store whether every substring of str is a palindrome or not during the preprocessing. With such a table, the function isPalindrome can verify the substring str[i,j] in O(1) time.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.