You are not logged in. Please login at www.codechef.com to post your questions!

×

CDZ14A - Editorial

PROBLEM LINKS:

Practice
Contest

Author: sikander_nsit
Tester: sikander_nsit
Editorialist: sikander_nsit

DIFFICULTY:

SIMPLE-EASY

PROBLEM:

Given a string consisting of three possible characters 'B', 'R' and 'G' find the length of the shortest substring such that it contains all three characters atleast once.

EXPLANATION:

This was an implementation based problem. There are numerous ways to do it. One way is to traverse the string and for each position calculate the answer if the substring ended at the current position. For this we can keep three variables to keep track of the most recent position of each pill. At each position update the most recent position of the current pill as the current index and calculate the answer by subtracting from this the minimum of the three values.
PSEUDOCODE

    arr['R']=arr['G']=arr['B']=-10000000;
    for(j=0;j<n;++j)
    {
        arr[str[j]]=j;
        num=j-min(arr['R'],min(arr['G'],arr['B']))+1;
        ans=min(ans,num);
    }

AUTHOR'S SOLUTION:

Author's solution can be found here.

This question is marked "community wiki".

asked 11 Feb '14, 03:33

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

edited 18 Apr '17, 22:08

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,191
×850
×10
×2

question asked: 11 Feb '14, 03:33

question was seen: 868 times

last updated: 18 Apr '17, 22:08