You are not logged in. Please login at to post your questions!


Hackerearth AVI Hiring Challenge


Can somebody help with this problem?

Expected Solution - O(n) alt text

asked 06 Nov '17, 00:41

anushi's gravatar image

accept rate: 15%

int calculate (string s) {
   int ans = 0;
   string s1,s2;
   for(int i=0;i<s.length()-1;i++) {
      s1 = s.substr(0,i+1);
      s2 = s.substr(i+1,i+1);
      if(s1 == s2)
    return ans;

answered 06 Nov '17, 01:10

shukrant's gravatar image

accept rate: 22%

edited 06 Nov '17, 01:13

All operations defined inside for loop (substr & ==) takes O(length of string) hence in worst case it would lead O(n^2).

(06 Nov '17, 09:15) anushi4★

It is simple. For every index in the string let F[i] denotes what is the length of longest prefix of the string that matches the substring of the string that starts at index i. Now you have to count total indices such that F[i] = i - 1 . This is because dividing by power of the 10 generates a prefix of the string. You can use Z algorithm for that.


answered 06 Nov '17, 08:52

apptica's gravatar image

accept rate: 17%

edited 06 Nov '17, 08:52

For every i this will take O(n) for comparison hence O(n^2).If you meant something different please explain..

(06 Nov '17, 09:14) anushi4★

Z algorithm can do this in O(n) time for all the indexes. Just have a read of that.

(06 Nov '17, 09:37) apptica5★

I solved this using hashing , you can check whether hash of both string are equal or not in O(1) after precomputation.


answered 06 Nov '17, 11:02

geeky_coder's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 06 Nov '17, 00:41

question was seen: 407 times

last updated: 06 Nov '17, 11:02