Test results - Codility

Tasks Details

hard

1. FillTheGaps

Given a string consisting of characters 'a', 'b' and/or '?', replace each '?' with 'a' or 'b' so that the longest fragment of the resulting string consisting of equal letters is as short as possible.

Task Score

100%

Correctness

100%

Performance

100%

You are given a string S of length N consisting of characters 'a' and 'b' with additional empty gaps represented by '?'. Your task is to replace every such gap with either an 'a' character or a 'b' character so that the longest fragment of S, consisting only of 'a' characters or 'b' characters, is as short as possible.

For example, for S = "aa??bbb", if you replace "??" with "aa", the longest fragment consisting of equal characters will have length 4: "aaaabbb". You can obtain a better result by replacing "??" with "ba", resulting in "aababbb". Then the longest fragment consisting of equal characters will have length 3.

Write a function:

def solution(s)

that, given a string S of length N, returns the minimum possible length of the longest fragment of S consisting of equal characters after replacing all "?" characters with letters.

Examples:

1. Given S = "aa??bbb", your function should return 3, as explained above.

2. Given S = "a?b?aa?b?a", your function should return 2. Question marks can be replaced in the following way: "aabbaabbaa".

3. Given S = "??b??", your function should return 1.

4. Given S = "aa?b?aa", your function should return 3.

Write an efficient algorithm for the following assumptions:

string S is made only of the following characters: 'a', 'b' and/or '?';

N is an integer within the range [1..100,000].

Solution

Programming language used Ruby

Time spent on task 2 minutes

Notes

not defined yet

Code: 18:40:11 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
    }
}

Code: 18:40:12 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
    }
}

Code: 18:40:24 UTC, rb, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

def solution(s)
  # write your code in Ruby 2.2
  arr = []
  prev_char = nil
  count = 0
  max_count = 0
  s.split("").each do |char|
    if prev_char.nil?
      prev_char = char
      count = 1
      next
    end
    if char == prev_char  
      count += 1
      next
    end
    # prev_char != char
    arr.push({char: prev_char, count: count})
    if prev_char != "?" and count > max_count
      max_count = count
    end
    prev_char = char
    count = 1
  end
  # push the last one too 
  arr.push({char: prev_char, count: count})
  if prev_char != "?" and count > max_count
    max_count = count
  end
  
  #puts arr.inspect 
  #puts max_count

  arr.each_with_index do |val, i|
    #puts "#{val.inspect} #{i}"
    if (val[:char] == "?")
      count_q = val[:count]

      left_val = i == 0 ? nil : arr[i-1] 
      right_val = arr[i+1]

      next if left_val.nil? or right_val.nil?

      next if count_q % 2 == 1 and left_val[:char] == right_val[:char]
      
      next if count_q % 2 == 0 and left_val[:char] != right_val[:char]
      
      min = left_val
      if right_val[:count] < min[:count]
        min = right_val
      end
      
      next if min[:count] > 2 and count_q > 1

      min[:count] += 1
      max_count = min[:count] if max_count < min[:count]
    end
  end

  [max_count,1].max

end

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.044 s

▶

example2
Second example test.

✔

0.044 s

▶

example3
Third example test.

✔

0.044 s

▶

example4
Fourth example test.

✔

0.044 s

expand all User tests

▶

test_data1

✔

0.044 s

OK
function result: 3

User test case 1:

['aa??aa']

Code: 18:40:52 UTC, rb, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

def solution(s)
  # write your code in Ruby 2.2
  arr = []
  prev_char = nil
  count = 0
  max_count = 0
  s.split("").each do |char|
    if prev_char.nil?
      prev_char = char
      count = 1
      next
    end
    if char == prev_char  
      count += 1
      next
    end
    # prev_char != char
    arr.push({char: prev_char, count: count})
    if prev_char != "?" and count > max_count
      max_count = count
    end
    prev_char = char
    count = 1
  end
  # push the last one too 
  arr.push({char: prev_char, count: count})
  if prev_char != "?" and count > max_count
    max_count = count
  end
  
  #puts arr.inspect 
  #puts max_count

  arr.each_with_index do |val, i|
    #puts "#{val.inspect} #{i}"
    if (val[:char] == "?")
      count_q = val[:count]

      left_val = i == 0 ? nil : arr[i-1] 
      right_val = arr[i+1]

      next if left_val.nil? or right_val.nil?

      next if count_q % 2 == 1 and left_val[:char] == right_val[:char]
      
      next if count_q % 2 == 0 and left_val[:char] != right_val[:char]
      
      min = left_val
      if right_val[:count] < min[:count]
        min = right_val
      end
      
      next if min[:count] >= 2 and count_q > 1

      min[:count] += 1
      max_count = min[:count] if max_count < min[:count]
    end
  end

  [max_count,1].max

end

Code: 18:40:53 UTC, rb, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

def solution(s)
  # write your code in Ruby 2.2
  arr = []
  prev_char = nil
  count = 0
  max_count = 0
  s.split("").each do |char|
    if prev_char.nil?
      prev_char = char
      count = 1
      next
    end
    if char == prev_char  
      count += 1
      next
    end
    # prev_char != char
    arr.push({char: prev_char, count: count})
    if prev_char != "?" and count > max_count
      max_count = count
    end
    prev_char = char
    count = 1
  end
  # push the last one too 
  arr.push({char: prev_char, count: count})
  if prev_char != "?" and count > max_count
    max_count = count
  end
  
  #puts arr.inspect 
  #puts max_count

  arr.each_with_index do |val, i|
    #puts "#{val.inspect} #{i}"
    if (val[:char] == "?")
      count_q = val[:count]

      left_val = i == 0 ? nil : arr[i-1] 
      right_val = arr[i+1]

      next if left_val.nil? or right_val.nil?

      next if count_q % 2 == 1 and left_val[:char] == right_val[:char]
      
      next if count_q % 2 == 0 and left_val[:char] != right_val[:char]
      
      min = left_val
      if right_val[:count] < min[:count]
        min = right_val
      end
      
      next if min[:count] >= 2 and count_q > 1

      min[:count] += 1
      max_count = min[:count] if max_count < min[:count]
    end
  end

  [max_count,1].max

end

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.044 s

▶

example2
Second example test.

✔

0.044 s

▶

example3
Third example test.

✔

0.044 s

▶

example4
Fourth example test.

✔

0.044 s

expand all User tests

▶

test_data1

✔

0.044 s

OK
function result: 2

User test case 1:

['aa??aa']

Code: 18:41:25 UTC, rb, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

def solution(s)
  # write your code in Ruby 2.2
  arr = []
  prev_char = nil
  count = 0
  max_count = 0
  s.split("").each do |char|
    if prev_char.nil?
      prev_char = char
      count = 1
      next
    end
    if char == prev_char  
      count += 1
      next
    end
    # prev_char != char
    arr.push({char: prev_char, count: count})
    if prev_char != "?" and count > max_count
      max_count = count
    end
    prev_char = char
    count = 1
  end
  # push the last one too 
  arr.push({char: prev_char, count: count})
  if prev_char != "?" and count > max_count
    max_count = count
  end
  
  #puts arr.inspect 
  #puts max_count

  arr.each_with_index do |val, i|
    #puts "#{val.inspect} #{i}"
    if (val[:char] == "?")
      count_q = val[:count]

      left_val = i == 0 ? nil : arr[i-1] 
      right_val = arr[i+1]

      next if left_val.nil? or right_val.nil?

      next if count_q % 2 == 1 and left_val[:char] == right_val[:char]
      
      next if count_q % 2 == 0 and left_val[:char] != right_val[:char]
      
      min = left_val
      if right_val[:count] < min[:count]
        min = right_val
      end
      
      next if min[:count] >= 2 and count_q > 1

      min[:count] += 1
      max_count = min[:count] if max_count < min[:count]
    end
  end

  [max_count,1].max

end

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.044 s

▶

example2
Second example test.

✔

0.044 s

▶

example3
Third example test.

✔

0.044 s

▶

example4
Fourth example test.

✔

0.044 s

expand all User tests

▶

test_data1

✔

0.044 s

OK
function result: 2

User test case 1:

['aa??aa']

Code: 18:41:28 UTC, rb, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

def solution(s)
  # write your code in Ruby 2.2
  arr = []
  prev_char = nil
  count = 0
  max_count = 0
  s.split("").each do |char|
    if prev_char.nil?
      prev_char = char
      count = 1
      next
    end
    if char == prev_char  
      count += 1
      next
    end
    # prev_char != char
    arr.push({char: prev_char, count: count})
    if prev_char != "?" and count > max_count
      max_count = count
    end
    prev_char = char
    count = 1
  end
  # push the last one too 
  arr.push({char: prev_char, count: count})
  if prev_char != "?" and count > max_count
    max_count = count
  end
  
  #puts arr.inspect 
  #puts max_count

  arr.each_with_index do |val, i|
    #puts "#{val.inspect} #{i}"
    if (val[:char] == "?")
      count_q = val[:count]

      left_val = i == 0 ? nil : arr[i-1] 
      right_val = arr[i+1]

      next if left_val.nil? or right_val.nil?

      next if count_q % 2 == 1 and left_val[:char] == right_val[:char]
      
      next if count_q % 2 == 0 and left_val[:char] != right_val[:char]
      
      min = left_val
      if right_val[:count] < min[:count]
        min = right_val
      end
      
      next if min[:count] >= 2 and count_q > 1

      min[:count] += 1
      max_count = min[:count] if max_count < min[:count]
    end
  end

  [max_count,1].max

end

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N * log(N)) or O(N)

expand all Example tests

▶

example1
First example test.

✔

0.044 s

▶

example2
Second example test.

✔

0.044 s

▶

example3
Third example test.

✔

0.044 s

▶

example4
Fourth example test.

✔

0.044 s

expand all Correctness tests

▶

simple
Simple hand-written cases. N <= 10.

✔

0.044 s

0.048 s

0.044 s

▶

random
Random test cases. N <= 10.

✔

0.044 s

▶

long_words
Tests containing long sequences of letters. N <= 15.

✔

0.044 s

▶

letters_of_equal_length
Segments of 'a' or 'b' of equal lengths separated by question marks. N <= 20.

✔

0.044 s

▶

segments_of_equal_length
Segments of characters of equal lengths. N <= 25.

✔

0.044 s

▶

shorter_around_longer
Lengths of segments of equal characters differ by at most 1. N <= 15.

✔

0.044 s

▶

corner_cases
Small corner cases. N <= 15.

✔

0.044 s

0.048 s

0.044 s

expand all Performance tests

▶

long_words_medium
Tests containing long sequences of letters. N <= 200. Score x 2.

✔

0.044 s

▶

big_random
Large random test cases. N = 50,000.

✔

0.104 s

0.088 s

0.072 s

0.092 s

0.104 s

0.108 s

▶

big_perf_package
Perfomance tests group. Score x 3.

✔

0.164 s

0.136 s

0.100 s

0.096 s

0.172 s

0.168 s

0.172 s