Changing 1 exactly 1 character to optimise a string

Question

1.00/5 (3 votes)

See more:

You are given a string S of lowercase English letters with length N. You are allowed to (but don't have to) choose one index in this string and change the letter at this index to any other lowercase English letter. The cost of this operation is the absolute value of the difference of ASCII values of the new letter and the original letter; let's denote it by X

Next, consider the number of pairs of indices (i,j)
in the resulting string (the string after changing one letter, or the original string if no letter was changed) such that 1≤i<j≤N and Si<Sj. Let's denote it by Y

Find the minimum possible value of X+Y?

For example
abcd answer is 6
dbca answer is 1
dcba answer is 0

as in dcba there is no pair (i,j) Si<Sj so answer is 0.

What I have tried:

i tried to change the minimum element to maximum and counted the number of pairs and also tried to changed maximum to minimum and counted pairs and printed min of all three.

Posted 8-Jul-18 8:23am

Member 13903102

Updated 8-Jul-18 11:10am

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2018-07-08T08:55:00

So, you show no attempt to solve the problem yourself, you have no question, you just want us to do your HomeWork.
HomeWork problems are simplified versions of the kind of problems you will have to solve in real life, their purpose is learning and practicing.

We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
Any failure of you will help you to learn what works and what don't, it is called 'trial and error' learning.
So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help.

As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
When you just ask for the solution, it is like trying to learn to drive a car by having someone else training.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

OriginalGriff · Answer 2 · 2018-07-08T08:58:00

Solution 2

We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think!

If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!

Posted 8-Jul-18 8:58am

OriginalGriff

Comments

Member 13903102 8-Jul-18 22:27pm

just wanted a little hint for the character changing part and i am really new here didn't know much about how to ask a proper question sorry for that..

OriginalGriff 9-Jul-18 1:29am

That's ok - but when you post up homework and show no attempt to do it yourself, you aren't going to get help anywhere! :laugh:

Member 13903102 9-Jul-18 2:03am

i tried it with more strategy and what i found out is that i have to continue if the elements are in decreasing order or constant but this strategy also failing as is S=cdce and i change 2nd c it won't be optimal as changing 1st c to e gives the optimal answer ... i am still trying but can you tell me am i going in the right direction?? and also is merge sort is of any help here/?? and sorry for posting the complete question

Member 13903180 · Answer 3 · 2018-07-08T11:10:00

Solution 3

This is a question from on-going challenge, I don't think it is appropriate to ask it while the challenge is going on.

Posted 8-Jul-18 11:10am

Member 13903180