#!/usr/bin/env python


class Solution(object):
    def encode(self, s):
        """Encodes a string with the shortest possible length in O(n^3) time.

        See problem description for encoding rules.
        """
        n = len(s)

        # Create an index where all O(n^2) possible substrings begin.
        index = dict()
        for i in range(n):
            for j in range(i, n):
                x = s[i:j + 1]
                if x not in index:
                    index[x] = set()
                index[x].add(i)

        # Each dp[i][j] reperesents the shortest encoding for s[i:j + 1].
        dp = [[None for _ in range(n)] for _ in range(n)]
        return self.encodeUtil(s, 0, n - 1, index, dp)

    def encodeUtil(self, s, i, j, index, dp):
        """Calculates the shortest encoding for s[i:j + 1].

        There are O(n^2) subproblems but each subproblem considers O(n) smaller
        subproblems so the overall runtime is O(n^3)."""
        n = j - i + 1
        if n < 5:
            # Cannot compress anything shorter than 5 characters.
            return s[i:j + 1]
        elif dp[i][j] is not None:
            return dp[i][j]

        # Default encoding is just the raw string.
        encoding = s[i:j + 1]

        # Consider all repeating prefix substrings.
        for k in range(i, j):
            # Count how many times x occurs back to back in s[i:j + 1].
            x = s[i:k + 1]
            count = 1
            start = i + len(x)
            while start in index[x]:
                count += 1
                start += len(x)

            # Compress the prefix.
            x = self.encodeUtil(s, i, k, index, dp)
            if count > 1:
                prefix = '%d[%s]' % (count, x)
            else:
                prefix = x

            # Compress the suffix.
            suffix = self.encodeUtil(s, start, j, index, dp)

            # Apply prefix and suffix if encoding with x as prefix is shorter.
            if len(prefix) + len(suffix) < len(encoding):
                encoding = prefix + suffix

        dp[i][j] = encoding
        return encoding


def main():
    print('Please run this solution on LeetCode.')
    print('https://leetcode.com/contest/leetcode-weekly-contest-12/problems/encode-string-with-shortest-length/')  # nopep8

if __name__ == '__main__':
    main()

@@ -233,298 +233,8 @@
 s)%0A%0A
-        # Create an index where all O(n%5E2) possible substrings begin.%0A        index = dict()%0A        for i in range(n):%0A            for j in range(i, n):%0A                x = s%5Bi:j + 1%5D%0A                if x not in index:%0A                    index%5Bx%5D = set()%0A                index%5Bx%5D.add(i)%0A%0A
     
@@ -404,23 +404,16 @@
 , n - 1,
- index,
  dp)%0A%0A  
@@ -439,31 +439,24 @@
 lf, s, i, j,
- index,
  dp):%0A      
@@ -993,28 +993,33 @@
     
-for k in range(i,
+k = i%0A        while k %3C
  j
-)
 :%0A  
@@ -1111,24 +1111,69 @@
  s%5Bi:k + 1%5D%0A
+            y = self.encodeUtil(s, i, k, dp)%0A
             
@@ -1180,17 +1180,17 @@
 count = 
-1
+0
 %0A       
@@ -1207,17 +1207,9 @@
  = i
- + len(x)
+%0A
 %0A   
@@ -1228,24 +1228,35 @@
 le s
-tart in index%5Bx%5D
+%5Bstart:start + len(x)%5D == x
 :%0A  
@@ -1317,32 +1317,36 @@
 x)%0A%0A            
+    
 # Compress the p
@@ -1368,98 +1368,41 @@
     
-x = self.encodeUtil(s, i, k, index, dp)%0A            if count %3E 1:%0A                prefix =
+    prefix = y if count == 1 else
  '%25d
@@ -1421,57 +1421,16 @@
 nt, 
-x
+y
 )%0A
+%0A
     
-        else:%0A                prefix = x%0A%0A
     
@@ -1456,24 +1456,28 @@
 the suffix.%0A
+    
             
@@ -1517,21 +1517,18 @@
 , j,
- index,
  dp)%0A%0A
+    
     
@@ -1547,26 +1547,8 @@
 ply 
-prefix and suffix 
 if e
@@ -1596,16 +1596,20 @@
         
+  
+  
 if len(p
@@ -1654,32 +1654,36 @@
                 
+    
 encoding = prefi
@@ -1694,16 +1694,362 @@
 suffix%0A%0A
+            # This is critical for speedup! Essentially if we have a prefix x%0A            # that repeats p times, we do not need to consider any prefixes%0A            # formed by repeating x p times. Why? Because without this we will%0A            # be performing unecessary (repeat) calls to get optimal suffix.%0A            k = i + len(x) * count%0A%0A
         

Fix Encode String with Shortest Length solution