[Google][LintCode] Next Closest Time

Problem: Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are valid. "1:34", "12:9" are invalid.

Example:

Input: "19:34"
Output: "19:39"
Explanation:
The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  
It is not 19:33, because this occurs 23 hours and 59 minutes later.

Input: "23:59"
Output: "22:22"
Explanation:
It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

Approach: Let's try to find out the next digit for each position in "HH:MM" from right to left. If the next digit is greater than current digit, return directly and keep other digits unchanged.

Here is the steps: (Let's take an example say "17:38")

• Retrieve all four digits from given string and sort them in asscending order,"17:38"->digits[] {'1', '3', '7', '8'}
• Call findNext() from the right most digit to left most digit, which actually try to find next greater digit from digits[](if exist) which is suitable for current position, otherwise return the minimum digit (digits[0]):
• "HH:M#": There is no upperLimit for this position (0-9). Just pick the next different digit in the sequence. In the example above,'8' is already the greatest one, so we change it into the smallest one (digits[0]i.e.'1') and move to next step. ("17:38" -> "17:31")
• "HH:#M": The upperLimit is '5' obviously (max 59 seconds). The next different digit for '3' is '7', which is greater than '5', so we can't take it, hence we take the smallest one digits[0]. ("17:31" -> "17:11")
• "H#:MM": the upperLimit depends on previous digit which is time[0]. If time[0] is '2', then upper limit is '3' (20 - 23) else no upperLimit (0-9). Here we have time[0] as '1', so we can choose any digit we want. The next digit for '7' is '8', so we change it and return the result directly. ("17:11" -> "18:11")
• "#H:MM": the upperLimit is'2' (00 - 23).

Implementation in C#:

        public string NextClosestTime(string time)

{

char[] result = time.ToCharArray();

char[] digits = new char[] {

                                time[0],

                                time[1],

                                time[3],

                                time[4] };

Array.Sort(digits);

result[4] = this.findSuitableDigit(

                            digits,

                            '9',

                            result[4]);

if (result[4] > time[4])

{

return new string(result);

}

result[3] = this.findSuitableDigit(

                            digits,

                            '5',

                            result[3]);

if (result[3] > time[3])

{

return new string(result);

}

result[1] = this.findSuitableDigit(

digits,

result[0] == '2' ? '3' : '9',

result[1]);

if (result[1] > time[1])

{

return new string(result);

}

result[0] = this.findSuitableDigit(

                            digits,

                            '2',

                            result[0]);

return new string(result);

}

private char findSuitableDigit(

char[] digits,

int upperLimit,

char currDigit)

{

if (currDigit == upperLimit)

{

return digits[0];

}

int i = 0;

while (i < digits.Length &&

                digits[i] <= currDigit)

{

++i;

}

if (i == digits.Length)

{

return digits[0];

}

return digits[i] > upperLimit ?

                digits[0] :

                digits[i];

}

Complexity: O(n) (The length is constant)

[LintCode][Facebook] One Edit Distance

Problem: Given two strings S and T, determine if they are both one edit distance apart.

One edit distance means doing one of these operation:

• insert one character in any position of S
• delete one character in S
• change any one character in S to other character

Example:

Input: s = "aDb", t = "adb"
Output: true
Explanation: change D to d in s

Input: s = "ab", t = "ab"
Output: false
Explanation: s and t are same.

Approach: We can use the standard Edit Distance algorithm and check if the result is 1 that will definitely work. Let's try some other approach too. We need to check the following:

1. If difference between length of s and t is more than 1 than we can safely return false.
2. If above difference is 1 then we just need to check if removal of one character in bigger string makes both the strings same.
3. If length of s and t are same than we just need to ensure that the number of places the characters are different in s and t is 1.

That's all!

Implementation in C#:

        public bool IsOneEditDistance(string s, string t)

{

if (s == t)

{

return false;

}

if (Math.Abs(s.Length - t.Length) > 1)

{

return false;

}

if (s.Length > t.Length)

{

return this.CanOneDeleteWork(s, t);

}

if (t.Length > s.Length)

{

return this.CanOneDeleteWork(t, s);

}

int diferences = 0;

for (int i = 0; i < s.Length; ++i)

{

if (s[i] != t[i])

{

++diferences;

if (diferences > 1)

{

return false;

}

}

}

return true;

}

private bool CanOneDeleteWork(string bigStr, string smallStr)

{

int length = smallStr.Length;

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

{

if (bigStr[i] != smallStr[i])

{

return bigStr.Substring(i + 1).Equals(

                        smallStr.Substring(i));

}

}

return true;

}

Complexity: O(m * n)

[Google][LintCode] Longest Substring with At Most K Distinct Characters

Problem: Given a string S, find the length of the longest substring T that contains at most k distinct characters.

Example:

Input: S = "eceba", k = 2
Output: 3 ("ece")

Input: S = "aa", k = 1
Output: 2 ("aa")

Approach: We will use Sliding Window approach here. We will increase the window till the number of unique characters in window is less than k. Obviously we will use a map here to keep track of it. We will also keep tracking of the max length by comparing the maxLength variable to the current window length.

Implementation in C#:

    public int LengthOfLongestSubstringKDistinct(string s, int k)

    {

        int start = 0, end = 0, maxLength = 0;

        Dictionary<char, int> charFreqMap = new Dictionary<char, int>();

        while (end < s.Length)

        {

            if (!charFreqMap.ContainsKey(s[end]))

            {

                charFreqMap[s[end]] = 0;

            }

            ++charFreqMap[s[end]];

            while (charFreqMap.Keys.Count > k)

            {

                --charFreqMap[s[start]];

                if (charFreqMap[s[start]] == 0)

                {

                    charFreqMap.Remove(s[start]);

                }

                ++start;

            }

            maxLength = Math.Max(maxLength, end - start + 1);

            ++end;

        }

        return maxLength;

    }

Complexity: O(n)

[Google][LintCode] Add Bold Tag in String

Problem: Given a string s and a list of strings dict, you need to add a closed pair of bold tag and to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

Example:

Input: s = "abcxyz123", target = ["abc", "123"]
Output: "<b>abc</b>xyz<b>123</b>

Input: s = "aaabbcc", target = ["abc", "123"]
Output: "<b>aaabbc</b>c

Approach: Here we will take a marking boolean array which will tell us whether the current character should be mark bold or not. You can look at the implementation to understand the solution which very much straight forward.

Implementation in C#:

        public static string AddBoldTag(string s, string[] dict) 

{

            int length = s?.Length ?? 0;

            if (length == 0)

            {

                return null;

            }

            bool[] bold = new bool[length];

            int currEnd = 0;

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

            {

                foreach(string word in dict)

                {

                    if (StartsWith(s, i, word))

                    {

                        currEnd = Math.Max(currEnd, i + word.Length);

                    }

                }

                bold[i] = i < currEnd;

            }

            StringBuilder sb = new StringBuilder();

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

            {

                if (bold[i] && (i == 0 || !bold[i - 1]))

                {

                    sb.Append("<b>");

                }

                sb.Append(s[i]);

                if (bold[i] && (i == length - 1 || !bold[i + 1]))

                {

                    sb.Append("</b>");

                }

            }

            return sb.ToString();

        }

private static bool StartsWith(string s, int index, string word)

        {

            for (int i = 0; i < word.Length; ++i)

            {

                if (index + i >= s.Length)

                {

                    return false;

                }

                if (s[index + i] != word[i])

                {

                    return false;

                }

            }

            return true;

        }

Complexity: O(n * w * lw) where n is the length of s, w is the number of strings in dict and lw is the length of the largest string in dict.