Thread: Substring Problem | Optimization needed

  1. #1
    Registered User
    Join Date
    Nov 2018

    Substring Problem | Optimization needed

    I need some help in solving this substring problem am dealing with, here's the problem:

    Find the longest substring in a string(that we input) that contains at least one character who's frequency is greater than or equal to the (length of that substring)/2..


    1<=n<=105 (length of string inputted)



    Sample test case 2: We can select the substring starting from index 1 to 13, here the frequency of b is 6 which is greater than or equal to 13/2=6(take floor value).

    Note that, there can be multiple possible substrings.

    My approach:

    I already tried the brute force method, but that is not very efficient way of dealing with this problem.. Any hints on how to deal with this,
    here's the brute force way:
    #include <iostream>
    #include <cmath>
    #include <algorithm>
    #include <limits>
    #include <vector>
    #include <bitset>
    #include <cstdlib>
    #include <cstdio>
    #include <cstring>
    #include <time.h>
    #include <list>
    #include <set>
    #include <map>
    #include <queue>
    #include <cctype>
    #include <list>
    #include <iterator>
    #include <iosfwd>
    using std::cin;
    using std::cout;
    int main() {
        int t;cin>>t;while(t--){  //test cases
            int n;cin>>n; //length of string
            string s;cin>>s; //string input
            int max_sub=-1;   //result
            for(int i=0;i<n;i++)
                    for(int len=1;len<=n-i;len++)
                        string s1=s.substr(i,len); //get all the sub strings(hence brute force)
                        map<char,int> m;  //map to find the frequencies
                        for(int j=0;j<s1.length();j++)  //take the substring
                            m[s1[j]]++;//count the frequency
                            int val=s1.length();
                            if(m[s1[j]=]=>=val/2)   // if found any character with freq >= (length of substring)/2 
                                    if(val>max_sub)  //check if length is greater than prev max value
                                        {max_sub=val;} //update
                                break;//break, since we need atleast one character(so only one chacter will do the job)
                cout<<max_sub<<"\n"; //print the result
        return 0;

  2. #2
    Registered User
    Join Date
    Dec 2018
    What do you mean "optimizaton needed"? A brute force "solution" isn't a solution in competitive programming at all. A monkey could write that. The whole point is to come up with a clever solution. And since this is from a currently-running contest, you are basically asking for someone to help you cheat. If you can't solve it, you lose. Period. That's what "contest" means.

    And what kind of a moron includes 15 unnecessary headers? Are you thinking at all???

    BTW, I see someone already helped you to cheat on another site. I'm going to see if I can report you on the contest site.

  3. #3
    Registered User
    Join Date
    Nov 2018
    I see... you have a lot of frustration in your life, and since, you are too much of a coward to deal with them, you go online and try to undermine other's work, cool good for you.. and who says bruteforce approach is not a solution in competitive coding, this just shows me how little you know about competitive coding, a dynamic programming uses bruteforce, every good algorithm arises from bruteforce. It's because of keyboard warriors like you who don't help anyone at all, but try to not get them help from others too. I see your other posts as well, never doing anything productive and just trying to troll on others. good luck mate, it's very easy to be brave online and ........ yourself in real. you don't need to help others if you want, but just shut yourself up, if you don't want to, nobody cares about your opinion anyways.. cheers.

  4. #4
    Registered User
    Join Date
    Dec 2018
    Blah blah blah. What a bunch of bull!!!

    I see your account was closed on the other site.
    Was that the admin (I doubt it) or was it your own cowardice?

    You are a loser, literally.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help needed with a problem
    By enderulusoy in forum C Programming
    Replies: 21
    Last Post: 12-14-2017, 10:25 AM
  2. Stuck on a problem. Help needed please.
    By sdbuilt in forum C Programming
    Replies: 5
    Last Post: 09-05-2012, 11:06 PM
  3. GCC Optimization problem
    By alby in forum C Programming
    Replies: 6
    Last Post: 09-22-2009, 09:31 PM
  4. longest common substring problem
    By Enchanter88 in forum C++ Programming
    Replies: 4
    Last Post: 09-29-2007, 11:02 AM

Tags for this Thread