Given two strings a and b, find whether any anagram of string a is a sub-string of string b

I know this is a fairly (old and) simple question. But what people do not realize is that it has a catch! I saw this question here and browsed through most of the solutions. Almost all of them (except the crazy ones where folks wanted to do brutal force search) would fail on a very simple case. And this question, is all about just that case

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {
  string src, tgt;
  std::getline(cin, src);
  std::getline(cin, tgt);
  vector<int> buf(256, 0);
  const int tot = src.size();
  for (int i = 0; i < src.size(); ++i) {
    buf[src[i]]++;
  }
  vector<int> tmp(256, 0);
  int start = -1, tmp_tot = 0, end = 0;
  for (int i = 0; i < tgt.size(); ++i) {
    const unsigned char ch = tgt.at(i);
    if (buf[ch] > 0) {
      if (tmp[ch] == buf[ch]) {
        if (tmp_tot > 256) {
          tmp.clear();
          tmp.resize(256, 0);
        } else {
          while (tmp_tot > 0) tmp[tgt[i - tmp_tot--]]--;
        }
        start = i;
        tmp[ch]++;
        tmp_tot = 1;
      } else {
        if (start == -1) start = i;
        tmp[ch]++;
        ++tmp_tot;
        if (tmp_tot == tot) end = i;
      }
    }
  }
  if (end > 0) {
    cout << start << "    " << end << std::endl;
  } else {
    cout << "Not found\n";
  }
  return 0;
}
Advertisements

Why did you take computer science

Funny things happen in life everyday. In my campus interview, the guy who was taking my technical interview was very impressed with me, so he promptly asked me Why did you take up Computer Science. I have already said it in an earlier post that sometimes our mind works too fast for us to believe it. Same thing happened to me after he asked that question, I tried to recall why did I take up computer science and after analysing my entire life and all my encounters with computers prior to my joining my college, I could not find one motivating instance which drove me crazy about computers. The only answer I could manage to think was because on my counseling date everybody around me was filling the Computer Science of the same college and even my dad asked me to do so. But this would not impress my interviewer, I figured, so I transformed the answer into I was interested in computers from childhood Actually I first saw a computer when I was in class 8th and touched it in class 10th and in 11th and 12th only heard music and saw movies on it. I even said I was always into mathematics and solving programming problems alongwith finding efficient solutions. This was somewhat true but I was never a problem solving person, in fact I hated mathematics and always scored the least in it. Besides, I have a strict policy Conserve the brain :). I always used to say to my friends, ” .. yaar kuch bhi karunga par zindagi main computer science kabhi nhi padhunga.. kaisa boor subject hai yaar… aur sala bas computer k samne baithe rho …ch**tia ki tarah..“. But now I had to somehow make this guy to believe that I was born to be a programmer and that given a choice between a hottie and a laptop, I would die for a laptop. Funny na .. we find chameleons attractive and amazing in childhood but as we grow we develop into a chameleon ourselves. 🙂 I was laughing inside while I gave that answer but I am a nice actor, I put up a good show and even he believed that I was made for computers and programming was my religion. Mission Successful.

Hope the one who interviewed me never visits this post 🙂

%d bloggers like this: