CODEWITHSUNDEEP
javaalgorithmsubstringtime-complexitycomplexity-theory
Shadow OverLoad
Shadow OverLoad

Reputation: 72

How to find numbers of valid subString using O(n) time complexity algorithm

so I'm in need of a java method that receives a String type variable, a char type variable and an int type variable:

public static int subStrMaxC(String s, char c, int k)

So this method's idea is to check how many subStrings are in the String s that start and end with the character c and has maximum k c characters inside them. while using time complexity of O(n) while n == s.length() adding the API documentation below:

/**
     * Checks how many Sub-Strings are within a given String that starts and ends with a given character and also has that character inside the Sub-String maximum a given amount of times.
     * @param s the String to check for the Sub-String within.
     * @param c the character to check the Sub-String according to.
     * @param k the amount of time that the given character has to be within every Sub-String.
     * @return the number of the valid Sub-Strings.
     * @timeComplexity O(n) n - the String's (s) length.
     * @SpaceComplexity O(1)
     */

for example: subStrMaxC("abcabcabc", 'c', 1); should return 3 because the valid subString are: "cabc" , "cabc" , "cabcabc"

here is my code but it doesn't return the right answers:

public static int subStrMaxC(String s, char c, int k) {
    int count = 0, toReturn = 0;
    for(int index = 0; index < s.length(); index++) {
        if(s.charAt(index) == c)
            count++;
    }

    while(k >= 0) {
        if(k == 0)
            return toReturn;
        else if(k % 2 == 0) {
            toReturn += count - (k + 1) - toReturn;
            k--;
        }
        else {
            toReturn += count / 2 - toReturn;
            k--;
        }
    }
    return toReturn;
}

Would love to get some help! Thanks !

Upvotes: 1

Views: 1444

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

We need to make few observations to solve this problem:

Assume that we have the longest valid substring that end at index ith, which contains x character c, with x <= k, so, in total, it contains x + 2 character c. We can say that, any substring that end at this index ith and start at any of the first x+1 character is a valid substring.

So, for each character c in the string, we just need to find the number of character c (denotes as count) that stand before it, if it greater than k + 1, just add k + 1 to the result, otherwise, just add count.

So here is the pseudo code: 

int result = 0;
int count = 0;
for(int i = 0; i < s.length(); i++){
    if(s.charAt(i) == c){
       result += Integer.min(k + 1, count);
       count++;
    } 
}

Time complexity: O(n)

Working demo: https://ideone.com/aUpxk5

Upvotes: 2

Related Questions