Heavy Alphabet

Limits: 1s, 256 MB

Lily’s father lives in Canada. He comes once in a year. But she thinks everyday about her father. She wants to gift him a beautiful string. To make the string she puts an alphabet in a little box everyday! Her father arrived home yesterday. Now she wants to give the string as a gift to him. While taking the box she felt that, the box of the string became too much heavy for her. She can’t lift it from the ground now. Then she decided to replace every consecutive identical characters except the first occurrence of that character with ”#” which isn’t heavy at all. As she is a little girl, she doesn’t care about the case sensitiveness of the alphabets as the weight of the uppercase and lowercase of a character is same.

This is a companion discussion topic for the original entry at https://toph.co/p/heavy-alphabet

what is the problem of my code??

for x in range(T):
a=[str(j) for j in S]
for i in range(0, len(a)):
if i==0:
if a[i]==a[i-1]:
print("".join(map(str, b)))

string s;

  cin >> s;

  map<char, bool> MAP;

  for (int i = 0; i < (int)s.size(); i++)

     s[i] = tolower(s[i]);

  ///cout << s << endl;

  for (int i = 0; i < (int)s.size(); i++)

     MAP[s[i]] = false;

  for (int i = 0; i < (int)s.size(); ++i)


     if (MAP[s[i]] == true)

        cout << "#";



        cout << s[i];

        MAP[s[i]] = true;


     if (s[i] != s[i + 1])


        MAP[s[i]] = false;

        MAP[s[i + 1]] = false;



  cout << endl;

i think it should work…where is the problem

when i wrote (int)strlen(s) it said tle
but when i wrote int length=strlen(s);
now it said ok ! whats the logic

for (int i = 0; i < (int)strlen(s); i++)

   s[i] = tolower(s[i]);

i tried it first …it said WA at test 3

then i tried to not make it lower at first rather compare like tolower(s[i]) ,
this time it is ok …whats the problem? i think this problem has a many problems inside it…i never faced these problems in any problem

Is there any problem?


strlen() runs in O(n)
So, every time you call strlen(s), then it finds the length of the string after n ± 1 (size of the string) iterations.
So, if size of the string is 10^5, then your code will need 10^10 iterations( for every iteration in the loop, strlen() is called) . It’s HUGE for 1 second!
But string class in C++ is not just char[]. size() or lenght() function in string class runs in O(1). Because as far as I know string object tracks the length of it’s string in a variable. Every time you call size() or length() function, it just returns the value of that variable.
So strlen(str) is not same as str.size() or str.length().

Try this input, you’ll understand:


output should be: