# Re: [ljc] Programming Coding Challenge Help

 From: Samir T. Sent on: Wednesday, June 6, 2012 1:10 AM
```Alexander seems to have cut out half the question. It appears that it's
all here:
http://www.leetco...­

— Samir.

> Hi Everyone
>
> I am doing some coding challenges and having difficulties understanding
> the solution to this problem.
>
> Can somebody help me understand the solution.
>
> Thanks
>
> To help illustrate this approach, I use a different example: *S* =
> “*acbbaca*” and *T* = “*aba*“. The idea is mainly based on the help of
> two pointers (begin and end position of the window) and two tables
> (/needToFind /and /hasFound/) while traversing *S*. /needToFind/ stores
> the total count of a character in *T* and /hasFound/ stores the total
> count of a character met so far. We also use a /count/ variable to store
> the total characters in *T* that’s met so far (not counting characters
> where hasFound[/x/]//excee­ds needToFind[/x/]). When count equals *T*‘s
> length, we know a valid window is found.
>
> Each time we advance the end pointer (pointing to an element /x/), we
> increment hasFound[/x/] by one. We also increment /count /by one if
> hasFound[/x/] is less than or equal to needToFind[/x/]. Why? When the
> constraint is met (that is, /count/ equals to *T*‘s size), we
> immediately advance begin pointer as far right as possible while
> maintaining the constraint.
>
> How do we check if it is maintaining the constraint? Assume that begin
> points to an element /x/, we check if hasFound[/x/] is greater than
> needToFind[/x/]. If it is, we can decrement hasFound[/x/] by one and
> advancing begin pointer without breaking the constraint. On the other
> hand, if it is not, we stop immediately as advancing begin pointer
> breaks the window constraint.
>
> Finally, we check if the minimum window length is less than the current
> minimum. Update the current minimum if a new minimum is found.
>
> Essentially, the algorithm finds the first window that satisfies the
> constraint, then continue maintaining the constraint throughout.
>
> <http://2.bp.blogs...;­
> i) *S* = “*acbbaca*” and *T* = “*aba*“.
>
> <http://4.bp.blogs...;­
> ii) The first minimum window is found. Notice that we cannot advance
> begin pointer as hasFound['a'] == needToFind['a'] == 2. Advancing would
> mean breaking the constraint.
>
> <http://3.bp.blogs...;­
> iii) The second window is found. begin pointer still points to the first
> element ‘a’. hasFound['a'] (*3*) is greater than needToFind['a'] (*2*).
> We decrement hasFound['a'] by one and advance begin pointer to the right.
>
> <http://2.bp.blogs...;­
> iv) We skip ‘c’ since it is not found in *T*. Begin pointer now points
> to ‘b’. hasFound['b'] (*2*) is greater than needToFind['b'] (*1*). We
> decrement hasFound['b'] by one and advance begin pointer to the right.
>
> <http://2.bp.blogs...;­
> v) Begin pointer now points to the next ‘b’. hasFound['b'] (1) is equal
> to needToFind['b'] (1). We stop immediately and this is our newly found
> minimum window.
>
> Both the begin and end pointers can advance at most /N/ steps (where /N/
> is *S*‘s size) in the worst case, adding to a total of 2/N/ times.
> Therefore, the run time complexity must be in /O/(/N/).
>
> |// Returns false if no valid window is found. Else returns|
> |// true and updates minWindowBegin and minWindowEnd with the|
> |// starting and ending position of the minimum window.|
> |bool||minWindow(||c­onst| |char||* S, ||const| |char| |*T,|
> |||int||&minWind­owBegin, ||int| |&minWindowEnd) {|
> |||int||sLen = ||strlen||(S);|
> |||int||tLen = ||strlen||(T);|
> |||int||needToFind[2­56] = {0};|
> |||for||(||int| |i = 0; i < tLen; i++)|
> |||needToFind[T[i]]+­+;|
> |||int||hasFound[256­] = {0};|
> |||int||minWindowLen­ = INT_MAX;|
> |||int||count = 0;|
> |||for||(||int| |begin = 0, end = 0; end < sLen; end++) {|
> |||// skip characters not in T|
> |||if||(needToFind[S­[end]] == 0) ||continue||;|
> |||hasFound[S[end]]+­+;|
> |||if||(hasFound[S[e­nd]] <= needToFind[S[end]])|­
> |||count++;|
> |||// if window constraint is satisfied|
> |||if||(count == tLen) {|
> |||// advance begin index as far right as possible,|
> |||// stop when advancing breaks window constraint.|
> |||while||(needToFin­d[S[begin]] == 0 |||
> |||hasFound[S[begin]­] > needToFind[S[begin]]­) {|
> |||if||(hasFound[S[b­egin]] > needToFind[S[begin]]­)|
> |||hasFound[S[begin]­]--;|
> |||begin++;|
> |||}|
> |||// update minWindow if a minimum length is met|
> |||int||windowLen = end - begin + 1;|
> |||if||(windowLen < minWindowLen) {|
> |||minWindowBegin = begin;|
> |||minWindowEnd = end;|
> |||minWindowLen = windowLen;|
> |||} ||// end if|
> |||} ||// end if|
> |||} ||// end for|
> |||return||(count == tLen) ? ||true| |: ||false||;|
> |}|
>
>
>
>
>
> --
> *everyone* on this mailing list ([address removed]
> This message was sent by alexander sharma ([address removed])
> from LJC - London Java Community
> <http://www.meetup...;­.
> <http://www.meetup...;­
> Set my mailing list to email me As they are sent
> <http://www.meetup...;­ | In one
> daily email
> <http://www.meetup...;­ | Don't
> send me mailing list messages
> <http://www.meetup...;­
>
> Meetup, PO Box 4668 #37895 New York, New York[masked] |
```

### London, United Kingdom

Founded Nov 26, 2007

#### Organizers:

Contact

• ##### Our Blog

Read the latest news from the LJC

• ##### RecWorks Ltd

Fixing Tech Recruitment using the Power of Community

• ##### jClarity

Java/JVM Performance Analysis Tools & mentoring for Java related matters

• ##### LJC Aggrity

Our LJC Aggrity site contains blog posts from our members

• ##### LJC Book Club

Our Book club with book reviews from our members

• ##### Devoxx UK

Java Community Conference, in collaboration with the LJC 12/13 Jun 14

• ##### SkillsMatter

"Host, help organise, promote, film many of our meetings."

• ##### New Relic

New Relic makes sense of billions of metrics a day in real time.

• ##### Hazelcast

Hazelcast is the leader in operating in-memory computing.

• ##### Java.Net

We are an official Java User Group recognised by Oracle's JUG program

• ##### O'Reilly

40% discount on printed books and 50% on e-books.

#### People in this Meetup are also in:

• ##### OpenTechSchool London

867 OpenTechSchool London Learners

• ##### Agile UX Meetup

1,791 Members

• ##### London Software Craftsmanship Community

2,951 Software Crafters

2,277 People

• ##### Big Data London

4,175 Data wiz'

776 Coders