Added more string solutions

Meto Trajkovski · Meto Trajkovski · commit 0bf441d71783 · 2019-11-08T15:39:51.000+01:00
diff --git a/README.md b/README.md
@@ -68,10 +68,12 @@ def name_of_problem_2(params):
 ###########
 # Testing #
 ###########
-# result = 'result'
+# Test 1
+# correct result => 'result'
 print(name_of_problem('example'))
 
-# result = 'result2'
+# Test 2
+# correct result => 'result2'
 print(name_of_problem_2('example2'))
 ```
 
diff --git a/Strings/anagram_indicies.py b/Strings/anagram_indicies.py
@@ -0,0 +1,95 @@
+'''
+Anagram indicies
+
+Given a word and a string S, find all starting indices in S which are anagrams of word.
+(An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once)
+
+Input: s='abxaba' word='ab'
+Output: [0, 3, 4]
+Output explanation: For example, given that word is 'ab', and S is 'abxaba', return 0 'ab', 3 'ab', and 4'ba'.
+
+=========================================
+Create a structure for counting the ferquency of letters (the structure is a simple dictionary).
+Similar to sliding window solution, add letters into the structure from the front of sliding window
+and remove from the back of sliding window.
+	Time Complexity: 	O(N)
+	Space Complexity: 	O(W)    , W = length of Word
+
+Solution 2: this can be solved using Rabin–Karp algorithm (small modification of this algorithm).
+But both solutions have same time & space complexity.
+'''
+
+
+############
+# Solution #
+############
+
+class LettersCounter:
+    def __init__(self):
+        self.__letters = {}
+    
+    def __create_if_not_exist(self, letter):
+        ''' helper method for creating a new field for the letter '''
+        if letter not in self.__letters:
+            self.__letters[letter] = 0
+    
+    def __delete_if_zero_letters(self, letter):
+        ''' helper deleting a letter from dictionary '''
+        if self.__letters[letter] == 0:
+            del self.__letters[letter]
+    
+    def add_letter(self, letter):
+        ''' increment the number of letters '''
+        self.__create_if_not_exist(letter)
+        self.__letters[letter] += 1
+        self.__delete_if_zero_letters(letter)
+
+    def remove_letter(self, letter):
+        ''' decrement the number of letters '''
+        self.__create_if_not_exist(letter)
+        self.__letters[letter] -= 1
+        self.__delete_if_zero_letters(letter)
+
+    def is_empty(self):
+        return len(self.__letters) == 0
+
+
+def anagram_indicies(s, word):
+    n = len(s)
+    w = len(word)
+    res = []
+
+    if n < w:
+        return res
+
+    counter = LettersCounter()
+    
+    # add all letters from the original word
+    for letter in word:
+        counter.add_letter(letter)
+
+    # remove first w letters from s string
+    for i in range(w):
+        counter.remove_letter(s[i])
+
+    if counter.is_empty():
+        res.append(0)
+    
+    for i in range(w, n):
+        # continue with the same logic, add letters from front and remove from the current index
+        counter.add_letter(s[i - w])
+        counter.remove_letter(s[i])
+
+        if counter.is_empty():
+            # if there are 0 elements into dictionary, then the word is anagram
+            res.append(i - w + 1)
+
+    return res
+
+
+###########
+# Testing #
+###########
+
+# correct result => [0, 3, 4]
+print(anagram_indicies('abxaba', 'ab'))
diff --git a/Strings/create_palindrome.py b/Strings/create_palindrome.py
@@ -0,0 +1,81 @@
+'''
+Create Palindrome
+
+Given a string, find the palindrome that can be made by inserting the fewest number of characters as possible anywhere in the word. 
+If there is more than one palindrome of minimum length that can be made, return the lexicographically earliest one (the first one alphabetically).
+
+Input: 'race'
+Output: 'ecarace'
+Output explanation: Since we can add three letters to it (which is the smallest amount to make a palindrome). 
+                    There are seven other palindromes that can be made from "race" by adding three letters, but "ecarace" comes first alphabetically.
+
+Input: 'google'
+Output: 'elgoogle'
+
+=========================================
+Solution explanation
+	Time Complexity: 	O(N)    , The solution looks like O(N^2) but that's not possible
+	Space Complexity: 	O(R)    , R = length of the new word (you need to the old string and allocate memory for that)
+'''
+
+
+############
+# Solution #
+############
+
+def create_palindrome(string):
+    n = len(string)
+
+    # find the biggest left palindrome, which starts from the first letter
+    max_left_palindrome = 1
+    for i in reversed(range(1, n)):
+        front = 0
+        back = i
+        found = True
+
+        while front <= back:
+            if string[front] != string[back]:
+                found = False
+                break
+            front += 1
+            back -= 1
+        
+        if found:
+            max_left_palindrome = i + 1
+            break
+
+    # find the biggest right palindrome, which starts from the last letter
+    max_right_palindrome = 1
+    for i in range(n - 1):
+        front = i
+        back = n - 1
+        found = True
+
+        while front <= back:
+            if string[front] != string[back]:
+                found = False
+                break
+            front += 1
+            back -= 1
+        
+        if found:
+            max_right_palindrome = n - i
+            break
+
+    # reverse the string using [::-1]
+    if max_right_palindrome > max_left_palindrome:
+        return string + string[-max_right_palindrome - 1::-1]
+    return string[:max_left_palindrome - 1:-1] + string
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# correct result => 'ecarace'
+print(create_palindrome('race'))
+
+# Test 2
+# correct result => 'elgoogle'
+print(create_palindrome('google'))
diff --git a/Strings/encoding_string.py b/Strings/encoding_string.py
@@ -0,0 +1,50 @@
+'''
+Encoding string
+
+Run-length encoding is a fast and simple method of encoding strings. 
+The basic idea is to represent repeated successive characters as a single count and character.
+Implement run-length encoding and decoding. You can assume the string to be encoded have no digits and consists solely of alphabetic characters. 
+You can assume the string to be decoded is valid.
+
+Input: 'AAAABBBCCDAA'
+Output: '4A3B2C1D2A'
+
+=========================================
+Simple solution, just iterate the string and count.
+	Time Complexity: 	O(N)
+	Space Complexity: 	O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def encoding(word):
+    n = len(word)
+    if n == 0:
+        return ''
+
+    letter = word[0]
+    length = 1
+    res = ''
+
+    for i in range(1, n):
+        if word[i] == letter:
+            length += 1
+        else:
+            res += str(length) + letter
+            letter = word[i]
+            length = 1
+    
+    res += str(length) + letter
+
+    return res
+
+
+###########
+# Testing #
+###########
+
+# correct result => '4A3B2C1D2A'
+print(encoding('AAAABBBCCDAA'))
diff --git a/Strings/longest_substring_with_distinct_characters.py b/Strings/longest_substring_with_distinct_characters.py
@@ -0,0 +1,62 @@
+'''
+Longest Substring With k Distinct Characters
+
+Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.
+
+Input: s = 'abcba', k = 2
+Output: 'bcb'
+
+=========================================
+Simple solution (like sliding window or queue, add to the end and remove from the front).
+    Time Complexity:    O(N)
+    Space Complexity:   O(N)
+'''
+
+
+############
+# Solution #
+############
+
+def longest_substring_with_distinct_characters(s, k):
+    letters = {}
+    longest = 0
+    length = 0
+
+    for i in range(len(s)):
+        if s[i] in letters:
+            # if this letter exists then only increase the counter and length
+            letters[s[i]] += 1
+            length += 1
+        else:
+            # if this letter doesn't exist then remove all discent letters from the front
+            # so the count of discent letters will be k-1
+            while len(letters) == k:
+                firstLetter = s[i - length]
+                letters[firstLetter] -= 1 # decrease the counter
+                if letters[firstLetter] == 0:
+                    # remove this letter from the dictionary because
+                    # in the susbtring there are no letters like this
+                    del letters[firstLetter]
+                length -= 1
+
+            # add the new letter in the dictionary
+            letters[s[i]] = 1
+            length += 1
+
+        # check if this length is the longest one
+        longest = max(longest, length)
+
+    return longest
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# correct result => 3
+print(longest_substring_with_distinct_characters('abcba', 2))
+
+# Test 2
+# correct result => 8
+print(longest_substring_with_distinct_characters('abcbcbcbba', 2))
diff --git a/Strings/longest_substring_without_repeating_characters.py b/Strings/longest_substring_without_repeating_characters.py
@@ -0,0 +1,55 @@
+'''
+Longest Substring Without Repeating Characters
+
+Given a string, find the length of the longest substring without repeating characters.
+
+Input: 'abcabcbb'
+Output: 3 
+Output explanation: The answer is 'abc', with the length of 3.
+
+Input: 'bbbbb'
+Output: 1
+Output explanation: The answer is 'b', with the length of 1.
+
+=========================================
+Simple string iteration, use hashset to save unique characters.
+If the current character exists in the set then move the left index till the one
+	Time Complexity: 	O(N)
+	Space Complexity: 	O(N)
+'''
+
+
+############
+# Solution #
+############
+
+def length_of_longest_substring(s):
+    unique_chars = set()
+    max_length = 0
+    left = 0
+    n = len(s)
+    
+    for i in range(n):
+        while s[i] in unique_chars:
+            # remove till the current char is unique
+            unique_chars.remove(s[left])
+            left += 1
+        
+        # in this moment you're sure that the current char is unique
+        unique_chars.add(s[i])
+        max_length = max(max_length, i - left + 1)
+        
+    return max_length
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# correct result => 3
+print(length_of_longest_substring('abcabcbb'))
+
+# Test 2
+# correct result => 1
+print(length_of_longest_substring('bbbbb'))
diff --git a/Strings/reverse_string.py b/Strings/reverse_string.py
@@ -1,7 +1,7 @@
 '''
-Reverse words in sentence
+Reverse string
 
-Reverse words in a given string, in constant space and linear time complexity.
+Reverse string, in constant space and linear time complexity.
 
 Input: 'i like this program very much' - In Python this should be a list (the string operations are slow/linear time)
 Output: 'hcum yrev margorp siht ekil i'
@@ -40,11 +40,11 @@ def reverse_sentence(sentence):
 # Test 1
 s = ['i', ' ', 'l', 'i', 'k', 'e', ' ', 't', 'h', 'i', 's', ' ', 'p', 'r', 'o', 'g', 'r', 'a', 'm', ' ', 'v', 'e', 'r', 'y', ' ', 'm', 'u', 'c', 'h']
 reverse_sentence(s)
-# correct result = ['h', 'c', 'u', 'm', ' ', 'y', 'r', 'e', 'v', ' ', 'm', 'a', 'r', 'g', 'o', 'r', 'p', ' ', 's', 'i', 'h', 't', ' ', 'e', 'k', 'i', 'l', ' ', 'i']
+# correct result => ['h', 'c', 'u', 'm', ' ', 'y', 'r', 'e', 'v', ' ', 'm', 'a', 'r', 'g', 'o', 'r', 'p', ' ', 's', 'i', 'h', 't', ' ', 'e', 'k', 'i', 'l', ' ', 'i']
 print(s)
 
 # Test 2
 s = ['h', 'o', 'w', ' ', 'a', 'r', 'e', ' ', 'y', 'o', 'u']
 reverse_sentence(s)
-# correct result = ['u', 'o', 'y', ' ', 'e', 'r', 'a', ' ', 'w', 'o', 'h']
+# correct result => ['u', 'o', 'y', ' ', 'e', 'r', 'a', ' ', 'w', 'o', 'h']
 print(s)
diff --git a/Strings/reverse_words_in_sentence.py b/Strings/reverse_words_in_sentence.py
diff --git a/Strings/zigzag_conversion.py b/Strings/zigzag_conversion.py
