Leetcode Random Challenge - Wk6 (Question5)

[Cicero]

Greetings,

Sorry I'm a bit late.

This week I've chosen a medium difficulty problem which I remember (vaguely) someone here mentioning they've had asked before in a technical interview, it had some traction with people commenting on his code etc. So it has some more relevance perhaps than the others.

5. Longest Palindromic Substring - https://leetcode.com/problems/longest-palindromic-substring/description/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"

Output: "bb"

How it works/Rules:

• We use the random question picker (sometimes), and all attempt it, one question a week.
• No cheating/looking at the editorial solution until your soln is accepted on leetcode, and you're convinced you can't get it any quicker.
• Language is up to you, this may help people appreciate other languages as well
• Only post your time taken, language, and percentage of submissions beaten at first. Use spoiler+php tags for your code.

 

[[)roi(]]

Here's a Swift 3 submission; beats 100% of submissions, time 43ms.
Note:

• Swift 3 String processing is quite slow re its enhanced Unicode support & lack of compiler optimisations (compared to C++, C, C#, Java, ...)
• Swift 4 String processing has both a substantially simplified API and many performance boosts. (but it's not supported by Leet yet)
• Local comparison (Swift 3 vs. Swift 4) with the same palindrome workload: 17ms vs 2.9ms.

Spoiler

fileprivate extension String
{
  /// String subscripting with Int ranges 
  /// ** Note: No longer required with Swift 4 (builtin) **
  ///
  /// - parameters:
  ///   - with: Range<Int> to use for extraction
  /// - returns: String extracted from range
  fileprivate func substring(_ range: CountableClosedRange<Int>) -> String?
  {
    guard let start = self.index(
      self.startIndex, offsetBy: range.lowerBound, limitedBy: self.endIndex),
      let end = self.index(
        self.startIndex, offsetBy: range.upperBound + 1, limitedBy: self.endIndex)
      else {
        return nil
    }
    return self.substring(with: start..<end)
  }
}

func longestPalindrome(_ s: String) -> String
{
  let charView = s.characters, c = charView.count
  guard c >= 2 else { return s }
  let chars = charView.map { String($0) }
  var m = (-1, -1), j = 0
  while j < c && c - j > m.1 / 2 {
    var i = (j, j)
    while i.1 < c - 1 && chars[i.1] == chars[i.1 + 1] { i.1 += 1 }
    j = i.1 + 1
    while i.1 < c - 1 && i.0 > 0 && chars[i.1 + 1] == chars[i.0 - 1] { i = (i.0 - 1, i.1 + 1) }
    _ = m.1 < i.1 - i.0 + 1 ? m = (i.0, i.1 - i.0 + 1) : ()
  }
  return s.substring(m.0...(m.0 + m.1 - 1)) ?? String(s.characters.first ?? " ")
}

 

[Cicero]

Couple of corner cases threw me a bit here, but managed a decent solution.

C, 3ms, beats 91.63%

Spoiler

char* longestPalindrome(char* s) {
    int l = strlen(s);
    int x, maxL, index, len;
    char *result;
    if (l < 2) return s;
    
    maxL = 0;
    for (int i=0, j=0; i<l; i++) {
        /* Check for duplicates */
        while (s[i]==s[++j]);
        if (i==0 && j>=l) return s;
        j--;
        
        x=1;
        while ( (s[i-x] == s[j+x]) && (x <= i) && ((x+j+1) < l) ) {
            x++;
        }
        /* Beyond array limits */
        if (s[i-x] == s[j+x]) x++;
        
        len = (j+x) - (i-x);
        if (len > maxL) {
            maxL = len-1;
            index = i-x+1;
        }
        /* Skip past duplicates */
        if (j!=i) i=j;
    }
    
    result = (char *)malloc (maxL+1);
    memcpy(result, &s[index], maxL);
    result[maxL] = 0;
    return result;
}

 

[Batista]

Nice well done!

 

[Cicero]

Here's a Swift 3 submission; beats 100% of submissions, time 43ms.
Note:

• Swift 3 String processing is quite slow re its enhanced Unicode support & lack of compiler optimisations (compared to C++, C, C#, Java, ...)
• Swift 4 String processing has both a substantially simplified API and many performance boosts. (but it's not supported by Leet yet)
• Local comparison (Swift 3 vs. Swift 4) with the same palindrome workload: 17ms vs 2.9ms.

Spoiler

fileprivate extension String
{
  /// String subscripting with Int ranges 
  /// ** Note: No longer required with Swift 4 (builtin) **
  ///
  /// - parameters:
  ///   - with: Range<Int> to use for extraction
  /// - returns: String extracted from range
  fileprivate func substring(_ range: CountableClosedRange<Int>) -> String?
  {
    guard let start = self.index(
      self.startIndex, offsetBy: range.lowerBound, limitedBy: self.endIndex),
      let end = self.index(
        self.startIndex, offsetBy: range.upperBound + 1, limitedBy: self.endIndex)
      else {
        return nil
    }
    return self.substring(with: start..<end)
  }
}

func longestPalindrome(_ s: String) -> String
{
  let charView = s.characters, c = charView.count
  guard c >= 2 else { return s }
  let chars = charView.map { String($0) }
  var m = (-1, -1), j = 0
  while j < c && c - j > m.1 / 2 {
    var i = (j, j)
    while i.1 < c - 1 && chars[i.1] == chars[i.1 + 1] { i.1 += 1 }
    j = i.1 + 1
    while i.1 < c - 1 && i.0 > 0 && chars[i.1 + 1] == chars[i.0 - 1] { i = (i.0 - 1, i.1 + 1) }
    _ = m.1 < i.1 - i.0 + 1 ? m = (i.0, i.1 - i.0 + 1) : ()
  }
  return s.substring(m.0...(m.0 + m.1 - 1)) ?? String(s.characters.first ?? " ")
}

Wow Droid, still can't really follow Swift at all.

Those are some serious improvements between Swift4 and 3, Leetcode should really get going on supporting that.

 

[[)roi(]]

Wow Droid, still can't really follow Swift at all.

Those are some serious improvements between Swift4 and 3, Leetcode should really get going on supporting that.

Not sure what part you find confusing, but let me try to explain some of this:

fileprivate extension String {
  // ... this stuff is in the middle is an unnecessary complex form of String computation; Swift 4 simplifies this
}

Anything in Swift can be extended, which quite often makes typical sub type polymorphism scenarios unnecessary. For example: You can extend protocols (interface / trait) and classes, structs, enums, etc... but as I said this particular extension isn't required in Swift 4; which makes Strings simpler to use and computationally faster; the goal being to make String processing as good (or even better) than Python.

Code bits like this are tuples, which are functionally similar to defining two separate variables of type int with an initial value of -1:

var m = (-1, -1)

Another way to think of Tuples is C structs, except without the need to define them before use; i.e. they're statically typed variables where the first field in the Tuple is accessed by using the .0 suffix and the second .1 and so on.

m.0 // refers to the first -1, and m.1 refers to the second -1
//Declaratively this is not different than defining two int variables, for example:
int m0 = -1, m1 = -1;

Note:In Swift Tuples can be of any length; quite similar to an array, except that each element can be statically typed differently, whereas an array is limited to a single type.

The other parts that might be confusing is the Optional type; for example:

// the substring extension function returns a
-> String?

The ? character indicates that the result is a String type that could either contain value or a null. Optional types are Union types which is basically defined as follows:

enum Optional<T> {
  case value(T)
  case none
}

Basically an Optional type is a generic container type that can either have a value or none; the functional equivalent of null. So defining any type with a ? as a suffix says that it can either contain a value of that type or a null. This is part of Swift's type safety. The Swift compiler ensures that all variables that aren't defined as optional types are initialized with a value (not be null), whereas those with the?; Optional suffix can be, but for type safety must be boxed in a container that basically forces the equivalent of null checking; in use it's however much similar than nulls.

And this bit of code:

return s.substring(m.0...(m.0 + m.1 - 1)) ?? String(s.characters.first ?? " ")

is simply an inline "inline ternary style" expression that deals with the possibility that the substring function could return a null. Basically the ?? operator returns the value if it's available or the alternative if it's not; but he first character in the String, could also be null, so we counter by returning a space -- roughly the ?? inline equivalent of an "or else" type operator.

and this is an inline Consumer type if statement

_ = m.1 < i.1 - i.0 + 1 ? m = (i.0, i.1 - i.0 + 1) : ()

Which is the same as this:

if m.1 < i.1 - i.0 +1 
{
  m = (i.0, i.1 - i.0 + 1)
}

The guard statement is an inverse a typical if statement:

guard c >= 2 else { return s }

This could be rewritten as either this:

if c>=2 {} else { return s }

or this:

if c<2 { return s }

The point of the guard statement is to break early on logic mismatches, and expressly to avoid the pyramid shaped code indentation that usually accompanies this type of branched code:

if (predicate1){
  if (predicate2) {
    if (predicate3 {
       // if predicate1 & predicate2 & predicate3 are a match
    }
    else {
      // if predicate1 & predicate2 but not predicate3 are a match
    }
  }
  else {
    // if predicate1 but not predicate2 & predicate3 are a match
  }
}

guard statements are a different syntactical approach to this i.e. we deal with this else logic up front; so after a guard we can assume a match; avoiding the typical (left to right) pyramid style code indentation. In practice it can do a lot more.

Anyway hope that helps with some of the confusion.

 

[Cicero]

Awesome thanks.