Skip to main content

Posts

Showing posts from April, 2021

Subsequence check

A subsequence of a string is a new string that is formed from the original string by removing zero or more characters without disturbing the relative positions of the remaining characters. Ex: Original String = ABC Subsequences = "", A, B, C, AB, AC, BC, ABC Characteristics of a Subsequence: 1. Length of subsequence is always less than or equal to the original string. 2. Characters should always appear in the same order as in the original string. 3. The total number of subsequences of a string with length n will be  2 n .  Since for every character we have 2 choices, either to keep it or remove it. func checkIs(subsequence: String , from input: String )-> Bool { guard subsequence. count <= input. count else { return false } var subsequenceIndex = subsequence. startIndex var inputIndex = subsequence. startIndex while inputIndex < input. endIndex && subsequenceIndex < subseque

Palindrome check

A Palindrome is a word, phrase, or sequence that reads the same backward as forward. Ex: RaceCar, madam, mom, level We have two methods to check for a palindrome. 1. Reverse String Comparision: If we reverse a string and compare it with the given string, then if both the strings are equal, we can say the given string is a palindrome. func reversedString(input: String )-> String { var reversed = "" for char in input{ reversed = "\(char)" + reversed } return reversed } func isPalindrome( _ input : String )-> Bool { let reversed = reversedString (input: input) return reversed == input } Time Complexity: θ(n) Space Complexity: θ(n) 2. Character Comparision: We'll start comparing the first character with the last character, if both are equal we'll increment the left index & decrement the right index until we cross the middle character. If we successfully pass the middle character then the given s