How to Solve ‘minSubstringWithAllChars’ in CodeFights

The Problem:

You have two strings, s and t. The string t contains only unique elements. Find and return the minimum consecutive substring of s that contains all of the elements from t.

It’s guaranteed that the answer exists. If there are several answers, return the one which starts from the smallest index.

Example

For s = "adobecodebanc" and t = "abc", the output should be
minSubstringWithAllChars(s, t) = "banc".

Input/Output

• [time limit] 4000ms (py)

• [input] string sA string consisting only of lowercase English letters.Guaranteed constraints:
  0 ≤ s.length ≤ 100.
• [input] string tA string consisting only of unique lowercase English letters.Guaranteed constraints:
  0 ≤ t.length ≤ min(26, s.length).
• [output] string

The Solution:

def minSubstringWithAllChars(s, t):
    for x in range(len(s)+1):
        for p in range(len(s)-x+1):
            c = filter(lambda x: x in t,s[p:p+x])
            if len(set(c))==len(t):
                return s[p:p+x]
    return ""

The Explanation:

How to Solve ‘isCryptSolution’ in CodeFights

The Problem:

A cryptarithm is a mathematical puzzle for which the goal is to find the correspondence between letters and digits, such that the given arithmetic equation consisting of letters holds true when the letters are converted to digits.

You have an array of strings crypt, the cryptarithm, and an an array containing the mapping of letters and digits, solution. The array crypt will contain three non-empty strings that follow the structure: [word1, word2, word3], which should be interpreted as the word1 + word2 = word3 cryptarithm.

If crypt, when it is decoded by replacing all of the letters in the cryptarithm with digits using the mapping in solution, becomes a valid arithmetic equation containing no numbers with leading zeroes, the answer is true. If it does not become a valid arithmetic solution, the answer is false.

Example

For crypt = ["SEND", "MORE", "MONEY"] and

solution = [['O', '0'],
            ['M', '1'],
            ['Y', '2'],
            ['E', '5'],
            ['N', '6'],
            ['D', '7'],
            ['R', '8'],
            ['S', '9']]

the output should be
isCryptSolution(crypt, solution) = true

When you decrypt "SEND", "MORE", and "MONEY" using the mapping given in crypt, you get 9567 + 1085 = 10652 which is correct and a valid arithmetic equation.

For crypt = ["TEN", "TWO", "ONE"] and

solution = [['O', '1'],
            ['T', '0'],
            ['W', '9'],
            ['E', '5'],
            ['N', '4']]

the output should be
isCryptSolution(crypt, solution) = false

Even though 054 + 091 = 145, 054 and 091 both contain leading zeroes, meaning that this is not a valid solution.

Input/Output

• [time limit] 4000ms (py)

• [input] array.string crypt

  An array of three non-empty strings containing only uppercase English letters.

  Constraints:
  crypt.length = 3,
  1 ≤ crypt[i].length ≤ 14.

• [input] array.array.char solution

  An array consisting of pairs of characters that represent the correspondence between letters and numbers in the cryptarithm. The first character in the pair is an uppercase English letter, and the second one is a digit in the range from 0to 9.

  Constraints:
  solution[i].length = 2,
  'A' ≤ solution[i][0] ≤ 'Z',
  '0' ≤ solution[i][1] ≤ '9',
  solution[i][0] ≠ solution[j][0], i ≠ j,
  solution[i][1] ≠ solution[j][1], i ≠ j.

  It is guaranteed that solution only contains entries for the letters present in crypt and that different letters have different values.

• [output] boolean

  Return true if the solution represents the correct solution to the cryptarithm crypt, otherwise return false.

The Solution:

The Explanation:

Map the letters to the given numbers.

Generate corresponding numbers,

if first + second = third, check if they have leading zeros by comparing the length of numbers and the words, if not, return 1

f they have leading zeros or the sum is not equal, return 0

How to Solve ‘containsCloseNums’ in CodeFights

The Problem:

Given an array of integers nums and an integer k, determine whether there are two distinct indices i and j in the array wherenums[i] = nums[j] and the absolute difference between i and j is less than or equal to k.

Example

• For nums = [0, 1, 2, 3, 5, 2] and k = 3, the output should be
  containsCloseNums(nums, k) = true.

  There are two 2s in nums, and the absolute difference between their positions is exactly 3.

• For nums = [0, 1, 2, 3, 5, 2] and k = 2, the output should be

  containsCloseNums(nums, k) = false.

  The absolute difference between the positions of the two 2s is 3, which is more than k.

Input/Output

• [time limit] 4000ms (py)

• [input] array.integer nums

  Constraints:
  0 ≤ nums.length ≤ 55000,
  -231 - 1 ≤ nums[i] ≤ 231 - 1.

• [input] integer k

  Constraints:
  0 ≤ k ≤ 35000.

• [output] boolean

The Solution:

The Explanation:

First of all, we can solve this by running two loops, one is i from 1 to k and the other j from 0 to len(nums)-i and compare nums[j] and nums[i+j]. If we find an equality, return 1. If none found, return 0.

However, we would receive Time Limit Exceeded Error. So, we need a better solution. We know that when we sort numbers, the same numbers will be consecutive in sorted order. So, if we store the original locations of all elements, we will have the same elements together and also know their original location. All we have to do now is to check if any consecutive equal numbers have a smaller distance than k+1.

This reduces our complexity from, let’s say len(nums) = n. Then, O(n*k) to O( n*log(n) )

limit of n is 55000 so, logn is approximately 16. Where k could be 35000. So, our worst case scenario becomes 55000*35000 to 55000*16.

How we do this is simple. First,generate a new array with numbers and their original addressses. Then, sort them using their values. Then, for each element, check if the previous element has the same value, if so, check their original location distances. If smaller than k+1, return 1

Otherwise, return 0

How to Solve ‘SimplifyPath’ in CodeFights

The Problem:

Given an absolute file path (Unix-style), shorten it to the format /<dir1>/<dir2>/<dir3>/....

Here is some info on Unix file system paths:

• / is the root directory; the path should always start with it even if it isn’t there in the given path;
• / is also used as a directory separator; for example, /code/fights denotes a fights subfolder in the code folder in the root directory;
  • this also means that // stands for “change the current directory to the current directory”
• . is used to mark the current directory;
• .. is used to mark the parent directory; if the current directory is root already, .. does nothing.

Example

For path = "/home/a/./x/../b//c/", the output should be
simplifyPath(path) = "/home/a/b/c".

Here is how this path was simplified:
* /./ means “move to the current directory” and can be replaced with a single /;
* /x/../ means “move into directory x and then return back to the parent directory”, so it can replaced with a single /;
* // means “move to the current directory” and can be replaced with a single /.

Input/Output

• [time limit] 4000ms (py)

• [input] string pathA line containing a path presented in Unix style format. All directories in the path are guaranteed to consist only of English letters.

  Constraints:
  1 ≤ path.length ≤ 5 · 104.

• [output] stringThe simplified path.

The Solution:

The Explanation:

How to solve ‘removeDuplicateAdjacents’ in CodeFights

The Problem

Given a string s, recursively remove any adjacent duplicate characters that it contains.

Example

• For s = "cooodefightssforrrcodee", the output should be
  removeDuplicateAdjacent(s) = "cdefightfocod".
• For s = "acaaabbbacdddd", the output should be
  removeDuplicateAdjacent(s) = "acac".

Input/Output

• [time limit] 4000ms (py)

• [input] string s

  A string composed of lowercase English letters.

  Constraints:

  1 ≤ s.length ≤ 50.

• [output] string

  A string obtained by removing all adjacent duplicates from the input string.

The Solution

The Explanation

CodeFights Problems

Stay tuned for more solution/explanations.

If you have a question you want to see the solution of, comment below so that I can help you!

Also, I figured out how to put actual code snippets with indentation and all, so, the newer ones will have the code as a text instead of an image.

How to Solve ‘treeLevelSum’ in CodeFights

The Problem

Given a binary tree and a number k, your task is to find the sum of tree nodes at level k. The binary tree is represented by a string tree with the format: (<node-value>(<left subtree>)(<right subtree>)).

Example

For tree = "(0(5(6()())(14()(9()())))(7(1()())(23()())))" and k = 2, the output should be

treeLevelSum(tree, k) = 44.

Explanation: The nodes at level 2 are 6, 14, 1, and 23, so the answer is 6 + 14 + 1 + 23 = 44.

Input/Output

• [time limit] 4000ms (py)

• [input] string tree

  A valid string representing a tree.

  Constraints:

  2 ≤ tree.length ≤ 105.

  All the values in a given tree are guaranteed to be integers.

• [input] integer k

  Constraints:

  0 ≤ k ≤ 105.

• [output] integer

  The total sum of all the values at level k in a tree.

The Solution

How to Solve ‘numberof1Bits’ in CodeFights

The Problem

Note: Avoid using built-in functions that convert integers to their binary representations. Write the solution that uses O(k)operations per test, where k is the number of bits set to 1.

Write a function that takes an unsigned (positive) integer and returns the number of 1 bits its binary representation contains. This value is also known as the integer’s Hamming weight.

Example

For n = 13, the output should be
numberOf1Bits(n) = 3.

13 is represented in binary as 1101, so the function should return 3.

Input/Output

• [time limit] 4000ms (py)

• [input] integer n

  Constraints:
  0 ≤ n ≤ 231 - 1.

• [output] integer

The Solution

The Problem

Sort the letters in the string s by the order they occur in the string t.

Example

• For s = "weather" and t = "therapyw", the output should be
  sortByString(s, t) = "theeraw";
• For s = "good" and t = "odg", the output should be
  sortByString(s, t) = "oodg".

Input/Output

• [time limit] 4000ms (py)

• [input] string s

  A string consisting only of lowercase English letters.

  Constraints:
  0 ≤ s.length ≤ 104.

• [input] string t

  A string consisting only of unique lowercase English letters. It is guaranteed that t contains all of the letters that occur in s.

  Constraints:
  0 ≤ t.length ≤ 26.

• [output] string

The Solution

How to solve ‘sortedSquaredArray’ in CodeFights

The Problem

Note: Come up with a linear solution, since that is what you would be asked to do in an interview.

You have a sorted array of integers. Write a function that returns a sorted array containing the squares of those integers.

Example

For array = [-6, -4, 1, 2, 3, 5], the output should be
sortedSquaredArray(array) = [1, 4, 9, 16, 25, 36].

The array of squared integers from array is: [36, 16, 1, 4, 9, 25]. When sorted, it becomes: [1, 4, 9, 16, 25, 36].

Input/Output

• [time limit] 4000ms (py)

• [input] array.integer array

  A sorted array of integers.

  Constraints:
  1 ≤ array.length ≤ 104,
  -104 ≤ array[i] ≤ 104.

• [output] array.integer

  A sorted array of integers composed of the squared integers from the input array.

The Solution