How do we model algorithms problems with math equations?-CodePudding

Mathematics has always been a prime tool for making abstract problems into tangible ones thus making their solution easier. let's take this problem from LeetCode:

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Is there a method to model this kind of problem or any problem with mathematic equations?

CodePudding user response：

Here is a solution that is linear in computing time (O(n)).

For convenience I have assumed that the letters are all lower case.

Suppose the string is as follows.

str = 'abacbdcb'

Begin by creating a hash whose keys are the lowercase letters of the alphabet and whose value for key 'k' is the index of the string at which the letter 'k' was last "seen" in the string (to be defined). Initially all values are nil, meaning no characters have been seen.

idx_last_seen = {"a"=>nil, "b"=>nil, "c"=>nil,..., "z"=>nil}

Create an array longest containing one element whose value is 1:

longest = [1]

longest[i] will be the length of the longest non-repeating string that ends at index i.

Index i = 0

Initialize the string index and update idx_last_seen:

i = 0
idx_last_seen[str[i]] = i

so now

idx_last_seen #=> {"a"=>0, "b"=>nil, "c"=>nil,..., "z"=>nil}

Index i = 1

Increment the string index and record the character in the string at that index:

i  = 1 #=> 1
c = str[i] #=> 'b'

We wish to now compute longest[i].

idx_last_seen[c] = idx_last_seen['b'] #=> nil

As idx_last_seen has no key c, c has not been seen before. Therefore, we append longest with the last element of longest plus 1.

longest << (longest[-1]   1)
  #=> [1, 2]

Here longest[-1] denotes the last element of longest.

This tells us that the length of the longest non-repeating string ending at index 0 is 1 and the longest non-repeating string ending at index 1 is 2.

Update idx_last_seen:

idx_last_seen[str[i]] = i
idx_last_seen
  #=> {"a"=>0, "b"=>1, "c"=>nil,..., "z"=>nil}

Index i = 2

i  = 1 #=> 2
c = str[i] #=> 'a'
j = idx_last_seen[c] = idx_last_seen['a'] #=> 0

j = 0 means that 'a' was last seen at index 0. Therefore the longest string ending at index 2 equals

i - j #=> 2

so we append 2 to longest and update idx_last_seen:

longest << i - j
  #=> [1, 2, 2]
idx_last_seen[c] = i
idx_last_seen #=> {"a"=>2, "b"=>1, "c"=>nil,..., "z"=>nil}

Index i = 3

i  = 1 #=> 3
c = str[i] #=> 'c'
idx_last_seen[c] = idx_last_seen['c'] #=> nil

so c has not been seen before. Therefore:

longest << (longest[-1]   1)
  #=> [1, 2, 2, 3]

Update idx_last_seen

idx_last_seen[c] = i
idx_last_seen #=> {"a"=>2, "b"=>1, "c"=>3, "d"=>nil,..., "z"=>nil}

Wrapping up

Continuing in this way we obtain the following results.

 01234567 
'abacbdcb'  longest
 1           'a'
  2          'ab'
   2         'ba'
    3        'bac'
     3       'acb'
      4      'acbd'
       3     'bdc'
        3    'dcb'
         3   'dab'
          2  'ba'
           3 'bac'

Each number on the diagonal equals the the length of the maximum non-repeating string that ends at the character of the string that is in the same column above; that is, they are the elements of longest. I've already shown the calculations for the first four indices. The string shown to the right of the each number on the diagonal is the associated longest non-repeating string ending at the associated index.

We see that the longest non-repeating string ends at the index i for which longest[i] is maximum, here 4, the string 'acbc'.