Can anybody suggest the solution in O(n)?

[SparkXV]

Two strings S and T of the same length N .Convert the string S into T by doing some operations. In an operation, you can delete the first character of the string S and append any character at the end of the string. You are required to determine the minimum number of operations to convert S into T .

Example:
7
S:aaxaabc
T:aabcaax

Output=3

[counter strike]

man just find lcs of two strings and do some manipulations.
Have you solved the minimum matrix question?

[Duthomhas]

aaxaabc
↕yes, n=0, k=0
aabcaax

aaxaabc
 ↕yes, n=0, k=1
aabcaax

aaxaabc
  ↕no, n=0, k=2
aabcaax

aaxaabc
  ↕no, n=2, k=0
  aabcaax
  
aaxaabc
   ↕yes, n=3, k=0
   aabcaax

aaxaabc
    ↕yes, n=3, k=1
   aabcaax

aaxaabc
     ↕yes, n=3, k=2
   aabcaax
     
aaxaabc
      ↕yes, n=3, k=3
   aabcaax
      
aaxaabc
       ↑done, n=3, k=4
   aabcaax
   
Answer := n = 3

Best case behavior = Ω(n)
Worst case behavior = O(2n) → O(n)
Hence, behavior = Θ(n)

[ne555]

aaxaabc
  ↕no, n=0, k=2
aabcaax

aaxaabc
  ↕no, n=2, k=0
  aabcaax

¿why did you advance two positions?

consider the case

s = aaaa...b
t = aaaa...a

you'll match everythin until you reach the last character, then fail.
so you move the string to the last character

aaaa...b
       aaaa...a

fail again and say that you need to replace all the character, when actually you could solve it by just removing the first
so, when you find a failure, ¿where do you start again?

[Duthomhas]

Convert S→T implies T is not mutable.
Basic text search algorithm.

[SparkXV]

@counter strike I am getting TLE by using lcs. can you help me out?

[SparkXV]

@Duthomhas @ne555 I used the lcs for two strings but getting time limit exceed.Can you guyz help me out?

[counter strike]

just do the minus between the lcs and the length of the string and take the minimum from that?
I got 80 marks for that.

[ne555]

> Convert S→T implies T is not mutable.
> Basic text search algorithm.
you start at position 'x', keep comparing until you fail, ¿what's the next position that you try?

advancing 'x' one by one would lead to O(n^2) in the worst case

for x in range(len(s)):
	if s[x:] == t[:-x]:
		return x

the example was incorrect, it should have been

t = aaaa...b
s = aaaa...a

remove the first character and add a 'b' at the end, one operation.
¿would your algorithm check that position?

[Duthomhas]

It seems I misread the 'append' part...

Sorry. :-(