SubString Question Tip

Key for Substring Questions is to use to pointer start & end til the substr = str[start:end] meets the condition.

So, you can use the template like below.



String minWindow(String givenStr, String target)


{

    //charCount is a map that holds counts of every character of target

    //it also means the numbers of each character that should be found in the substring

    Map<Character, Integer> charCount = new HashMap<Character, Integer>();


    for (int  i = 0;  i < 128; i++)

    {

        charCount.put((char)i, 0)

    }


    for(char c : givenStr.toCharArray())

    {

        charCount.put(c, charCount.get(c) + 1);

    }


    int start = 0; //pointer used for iteration


    int end = 0; //pointer used for iteration


    int counter = 0; //counter used to determine whether the window is valid, can vary(by the condition)

    //in this case, number of chars of target found in givenStr


    int subStart = 0; //variable that saves the head of substring to return


    int subLen = Integer.MAX_VALUE; //variable that saves the length of substring to return, can vary(minimun length or maximum length)

    //in this case, Integer.MAX_VALUE


    int size = givenStr.length();



    //outer loop moves the 'end' forward to find the valid window

    //if the window is valid, it pauses and proceeds into the inner loop

    while (end < size)

    {

    // manipulate counter properly

    // in this case, increase counter if a character of end exists belongs to the target

    Character endChar = givenStr.charAt(end);


    if (charCount.get(endChar) > 0)

    {

        counter++;

    }


    //change the charCount relevantly

    charCount.put(endChar, charCount.get(endChar) - 1);


    //change end for the next iteration

    end++;


    


    //when the window is valid, proceed into the inner loop(loop for 'start')

    //inner loop moves start forward to find optimal substring

    // in this case, take off the characters of the front to make the minimum length substring

    while(counter  == target.length())

    {

        //if current (start/end) has shorter length than the previous subLen, update the subLen

        //if this is about maximum length, it should be located in the line 'A'

        if ((end - start) < subLen) 

        {

            subStart = start;

            subLen = end - start;

        }    


       //change the charCount relevantly

        Character startChar = givenStr.charAt(start);

        charCount.put(startChar, charCount.get(startChar) + 1);


        //manipulate counter properly

        //in this case, decrease counter if a character of start belongs to the target

        if (charCount.get(startChar) > 0)

        {

            counter--;

        }


        //change start for the next iteration

        start++;

    }

    //A

    //For maximum length, the update should happen after the inner loop ends.

    }


    // if the iterations over, return the substring by acquired subStart and subLen

    if (subLen != Integer.MAX_VALUE)

        return givenStr.substring(subStart, subStart + subLen);

    else

        return "";

}


댓글

댓글 쓰기

이 블로그의 인기 게시물

Interface of Java

 You can define(declare + initialize) variable like interface_name variable_name = new class_name() In such cases, the variable can only use method overriding the interfaces methods. Also, the language does not recognized it as the class; the language recognizes it as interface. Still, it does have member variables of the class and there are some libraries that enables the programmer to tell what class it is constructed(i.e. Reflection) Interface can be used as parameter of functions or return types of functions. When interface is a parameter, the class that implements the interface should be given to the function. When interface is a return type, it can be used for polymorphism. Also, variable of java(in case its not primitive type like int, float), it is rather closer to pointer of C++; it refers to the value, not contains value itself. The important point is that, when the class implements the interface, all of its public methods should be the interface's methods. If not, client...
자세한 내용 보기

Data Analytics Overview(OLTP vs OLAP)

You’ve likely heard about the lucrative careers of high-level Data Analysts, but have you ever wondered how they actually handle "Big Data"? Of course, they aren’t just using Microsoft Excel. To understand the technology behind it, we must first distinguish between the two primary ways we process information:  OLTP  and  OLAP . 1. OLTP OLTP (Online Transactional Processing)  is the DB used for company’s daily operations. Whenever you post on Reddit or place an order on Amazon, you are interacting with an OLTP database. It is triggered by the business's customer and handled by the backend server so that it can provide the business. Fast:  It handles millions of requests with millisecond response times. Small&Frequent:  It focuses on small, frequent transactions—usually just a few rows at a time. Write-intensive:  Its primary job is to record or update new data as it happens. 2. OLAP OLAP (Online Analytical Processing)  is the very technology we...
자세한 내용 보기

Leetcode

이미지
1. Two Sum: find a pair with specific sum   class Solution : def twoSum ( self , nums : List [ int ] , target : int ) - > List [ int ] : numMap = { } n = len ( nums ) # Build the hash table for i in range ( n ) : numMap [ nums [ i ] ] = i # Find the complement for i in range ( n ) : complement = target - nums [ i ] if complement in numMap and numMap [ complement ] != i : return [ i , numMap [ complement ] ] return [ ] # No solution found You might wonder how does the code deals with duplicates. As you can see, in the iteration of building the hash table, always the latter(with bigger index) will be saved in the hash table. In the latter iteration finding the complement, the former one(with smaller index) always goes through the iteration earlier, so the [i, numMap[complement]] can return two different indexes, carrying duplicate...
자세한 내용 보기