Share C++/C# (16ms/152ms) explained solution using a direct address table instead of builtin dictionary


  • 4
    O

    C++ Solution

    int LengthOfLongestSubstring(string s)
    {
      if (s.size() == 0)
            return 0;
          const int characterMax = 256;
          // Let us create a hashtable where char is the key and position in the string
          // is the value. We have 256 different caracters
          int hashtable[characterMax] = {-1};
          // Let us initialize the hash table value to -1
          int i = 0;
          for (i = 0; i <characterMax; ++i)
          {
            hashtable[i] = -1;
          }
    
          int longest = 0;
          int substringStartPosition = 0;
          i = 0;
          for (i = 0; i < s.size(); ++i)
          {
            char c = s[i];
            if (hashtable[c] != -1)
            {
              // found a repeat character                  
              // keep the length if more than the previous value
              longest = (int) std::max(longest, i - substringStartPosition);
    
              // reset the hashtable value for all caracters that are 
              // before previous c position
              for(int j = substringStartPosition; j < hashtable[c]; ++j)
              {
                hashtable[s[j]] = -1;
              }
    
              // Move the start position
              substringStartPosition = hashtable[c] + 1;
            }
    
            hashtable[c] = i;
          }
    
          // keep the length if more than the previous value
          return std::max(longest, i - substringStartPosition);
        }
    

    C# solution

    public int LengthOfLongestSubstring(string s)
    {
      if (s == null)
        return 0;
      // Let us create a hashtable where char is the key and position in the string
      // is the value. We have 256 different caracters
      int[] hashtable = new int[256];
      // Let us initialize the hash table value to -1
      int i = 0;
      for (i = 0; i <hashtable.Length; ++i)
      {
        hashtable[i] = -1;
      }
    
      int longest = 0;
      int substringStartPosition = 0;
      i = 0;
      while (i < s.Length)
      {
        char c = s[i];
        if (hashtable[c] != -1)
        {
          // found a repeat character                  
          // keep the length if more than the previous value
          longest = System.Math.Max(longest, i - substringStartPosition);
    
          // reset the hashtable value for all caracters that are 
          // before previous c position
          for(int j = substringStartPosition; j < hashtable[c]; ++j)
          {
            hashtable[s[j]] = -1;
          }
    
          // Move the start position
          substringStartPosition = hashtable[c] + 1;
        }
    
        hashtable[c] = i;
        ++i;
      }
    
      // keep the length if more than the previous value
      return System.Math.Max(longest, i - substringStartPosition);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.