Blind 75

The Problem Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string. Examples Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". Constraints 1 <= s.length <= 1000 s consists of lowercase English letters. Brute Force Solution func countSubstrings(_ s: String) -> Int { let n = s.count let sArray = Array(s) var res = 0 for i in 0 ..< n { for j in i ..< n { var l = i var r = j while l < r && sArray[l] == sArray[r] { l += 1 r -= 1 } res += (l >= r) ? 1 : 0 } } return res } Explanation We can solve this problem by understanding how a brute-force approach works and then optimizing it. ...

The Problem Given a string s, return the longest palindromic substring in s. A string is palindromic if it reads the same forward and backward. Examples Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. Input: s = "cbbd" Output: "bb" Constraints 1 <= s.length <= 1000 s consists of only digits and English letters. Brute Force Solution func longestPalindrome(_ s: String) -> String { let sArray = Array(s) var res = "" var resLen = 0 let n = s.count for i in 0 ..< n { for j in i ..< n { var l = i var r = j while l < r && sArray[l] == sArray[r] { l += 1 r -= 1 } if l >= r && resLen < (j - i + 1) { res = String(sArray[i ..< j + 1]) resLen = j - i + 1 } } } return res } Explanation In the first example, we are given the input "babad". Let’s visualize it and try to find the longest palindromic substring. ...

The problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses in this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses are broken into on the same night. ...

The Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected, and they will automatically contact the police if two adjacent houses are broken into on the same night. Given an integer array nums representing the amount of money in each house, return the maximum amount of money you can rob tonight without alerting the police. ...

The problem You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Examples Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step Constraints 1 <= n <= 45 Brute Force Solution func climbStairs(_ n: Int) -> Int { func dfs(_ i: Int) -> Int { if i >= n { return i == n ? 1 : 0 } return dfs(i + 1) + dfs(i + 2) } return dfs(0) } Explanation Let’s visualize and look at the first example Input: n = 2, You can see that we can take two single steps or we can take one double step at once and find out that we have two different ways to solve this problem. ...