Tessellate S.T.E.M.S - Computer Science - School - Set 1 - Subjective Problem

You are given a string comprised of symbols a and b. You have to perform certain operations on it.

In each operation, you must select an occurrence of the substring ab in the string and replace it with bba. You must keep doing such operations until there is no occurrence of the string ab.

The task for this problem is to: Give an algorithm, whose input is such a string, and which computes the minimum number of operations until the string is free of occurrences of ab.

This problem is a part of Tessellate S.T.E.M.S.

#ComputerScience

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

What should be the time complexity of the solution?

Vatsal Sharma - 3 years, 5 months ago

Try coming up with the best solution that you can :)

Agnishom Chattopadhyay - 3 years, 5 months ago

How do we need to answer above question? Write theory explaining the stuff or the pseudocode?

Vatsal Sharma - 3 years, 5 months ago

@Vatsal Sharma – You are expected to describe the algorithm, possibly in the form of a pseudo-code, and describe why it is correct. Also, analyze the performance of the algorithm.

Agnishom Chattopadhyay - 3 years, 5 months ago

@Agnishom Chattopadhyay – So will you allot non-binary scores on subjective task according to the answer's quality? Proving the algorithm(sometimes greedy) is sometimes hard.

Vatsal Sharma - 3 years, 5 months ago

@Vatsal Sharma –

So will you allot non-binary scores on subjective task according to the answer's quality?

Yes. I will check with the organizers and clarify this point.

Proving the algorithm(sometimes greedy) is sometimes hard.

I agree. However, if an algorithm designer does not prove his algorithm, how does one know that what he has proposed really does what we want it to? That said, a next best thing to a proof would be some kind of heuristic justification of why you'd think that the algorithm is correct.

Agnishom Chattopadhyay - 3 years, 5 months ago

@Agnishom Chattopadhyay – "Hard problems make people think, and once in a while, it's not a horrible thing to think" - Vikraman Balaji

We stand by Balaji's words and believe that it is only through hard problems that one can assess understanding. Please give your best to the response. There will be points for the approach and the solution, and not just the answer.

Thank you On behalf of S.T.E.M.S Aalok

Aalok Thakkar - 3 years, 5 months ago

can the algorithm be a computer code of c++ format like with for loops and while loops and array along with basic string functions

BINIT KUMAR MONDAL - 3 years, 5 months ago

– You are expected to describe the algorithm, possibly in the form of a pseudo-code, and describe why it is correct. Also, analyze the performance of the algorithm.

Agnishom Chattopadhyay

Vatsal Sharma - 3 years, 5 months ago

1: str= stored string 2: str1="" 3: i=0 4: f=0 5: while (i< length of str) 6: c= character of str at i th position 7: if (c='a') f=f+1 8: elseif (c='b' and f>0) str1=str1+"bb" 9: elseif (c not equal to 'b' and f>0) str1=str1+'a', f=0 10: if (c not = 'a' or c not = 'b') str1=str1+c 11: i=i+1 12: end of while loop 13: return str1

Debayan Ganguly - 3 years, 5 months ago

Algorithim !!!!

Dipankar Dutta - 3 years, 5 months ago

What is the answer

Niranjan Sarode - 3 years, 5 months ago

1: str= stored string
2: str1=""
3: i=0
4: f=0
5: while (i< length of str)
6: c= character of str at i th position 
7: if (c='a') f=f+1
8: elseif (c='b' and f>0) str1=str1+"bb" 
9: elseif (c not equal to 'b' and f>0) 
                 str1=str1+'a',    f=0
10: if (c not = 'a' or c not = 'b') 
               str1=str1+c
11: i=i+1
12: end of while loop
13: return str1

Debayan Ganguly - 3 years, 5 months ago

if any flaw please reply

Debayan Ganguly - 3 years, 5 months ago

The logic is that check the number of b's after a and then replace 2x number of b's before a removing those b's

Debayan Ganguly - 3 years, 5 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$