How to calculate distance between 2 of the same charcaters in any string

Question

Create a function that can determine the longest substring distance between two of the same characters in any string. Ex: The longest distance in "meteor" is 1 (between the two e's). The longest distance in "abbba" is 3 (between the a's).  Do not use any built-in .NET framework utilities or functions (e.g. IndexOf, Substring, etc). 

Please help.(this is not a home wrok, just learning C#)

Thanks

Answer 1

It looks like homework, you should do by your own. But for help, you can use a loop thought every character and while looping increment one integer variable for example, until the loop reach next character identical to this one.

---

Web Developer

Answer 2

I would first ask the question of, "what's the longest distance between any two "a" characters in a particular string.  Once you perform the code for one particular letter you can simply execute that code for each letter in the alphabet.

Answer 3

With some more logic you can store each characters of the string in an array of 2 dimention A[character][character position].

Loop through this array. Take the first char and then compare it with all the characters after this char until a match is found.

If a match is found then subtract characters distance that will give you that char distance.

Repeat this for the next char and comparing it with the other chars next to it( no need to compare it with previous chars)...

The largest number would be the answer.

---

Mark it as helpful if so!!! thanks, Mithilesh

Answer 4

Should "abbabba" result in 5 or 2?

Answer 5

You should always compare with the char you start from.

In this case when you start from 'a' comparing till the last 'a' its 5 and then again with the second 'a' starting till the last 'a' its 2. You have to take the max value.

Hope am right?

---

Mark it as helpful if so!!! thanks, Mithilesh

Answer 6

That was kinda fun.

using System;

class Program
{
    static void Main( string[] args )
    {
        string[] tests = new string[] {
            @"meteor",
            @"abbba",
            @"This is a test",
            @"nomatch",
            @"please help me",
            @"aab1bc333cd22d",
        };

        foreach( string test in tests )
        {
            int n = FindLongest( test );
            Console.WriteLine( "{0} {1}", n, test );
        }
    }

    /// <summary>
    /// Finds the longest possible substring of length 2 or more that starts
    /// and ends with the same character.
    /// </summary>
    /// <param name="str">The string to search.</param>
    /// <returns>The index of the start of the longest substring.  
    /// Returns -1 if no such substring exists.
    /// This happens when there are no duplicate characters in the string.</returns>
    static int FindLongest( string str )
    {
        int best_i = -1;
        int best_length = 0;

        for( int i = 0; i < str.Length - best_length; ++i )
        {
            char c = str[i];
            for( int j = str.Length - 1; j > i + best_length; --j )
            {
                if( str[j] == c )
                {
                    best_i = i;
                    best_length = j - i;
                    break;
                }
            }
        }
        return best_i;
    }
}

Hopefully it's a no-brainer to return best_length instead of best_i.  Or best_length - 1 (as per your definition of length: abbba = 3), or both best_i and best_length - 1, or whatever you want to return.

But I suggest you work through problems like this yourself to get maximum benefit out of your assignment.  I purposely didn't describe the algorithm I used so that you can still do some of the thinking yourself.

Answer 7

Hi Wyck,

Tried your program and getting the output as:


String- meteor, Max- 1
String- abbba, Max- 0 (why 0, it should be 4)
String- This is a test, Max- 3
String- nomatch, Max- -1
String- please help me, Max- 2(why 2?)
String- aab1bc333cd22d,Max- 5                                                                                                                 

Is this the correct output for the test strings?Please clarify?

I tried with different logic as below:

private int FindLongest(string strVal)
        {
            int startVal = 0;
            int maxLength = 0;
            bool found = false;
            for (int i = 0; i <= strVal.Length; i++)
            {
                
                maxLength = 0;
                for(int k = i;k<strVal.Length-1;k++)
                {
                    if (strVal[i] == strVal[k + 1])
                    {
                        
                        found = true;
                    }
                    else
                        found = false;
                    if (found)
                        maxLength = k+1 - i;
                
                }
                if(maxLength>startVal)
                startVal = maxLength;
            }
            return startVal;
        }

try the above code and let me know if this is correct, i got the correct output as expected.

---

Mark it as helpful if so!!! thanks, Mithilesh

Answer 8

Simple answer: you cannot.

You need at least the string's indexer and its Length property, or its GetEnumerator method.

Answer 9

Hi, Here is very simply way

private int LongLen(string s, char c)
{
    int i = s.IndexOf(c);
    int j = s.LastIndexOf(c);
    return j - i;
}

Now to use this function, example:

int Ld = LongLen("abbba",'a');  //returns 3

Best wishes.

Answer 10

Hi Wyck,

Tried your program and getting the output as:


String- meteor, Max- 1
String- abbba, Max- 0 (why 0, it should be 4)
String- This is a test, Max- 3
String- nomatch, Max- -1
String- please help me, Max- 2(why 2?)
String- aab1bc333cd22d,Max- 5                                                                                                                 

Is this the correct output for the test strings?Please clarify?

Yes,  if you read my documentation, you'll see that in the example I chose to return from my function the 0-based index of the start of the longest substring, or -1 if it doesn't exist.

As I mentioned, you could return the length instead of the start index.  It's up to you.

meteor : 1  (the 'e')
 ^-*
01
abbba : 0  (the 'a')
^---*
0
This is a test : 3  (the 's' because 'T' doesn't match 't')
   ^--------*
0123
nomatch : -1  (no duplicate letters)
please help me : 2  (the 'e')
  ^----------*
012
aab1bc333cd22d : 5  (the 'c')
     ^---*
012345

 

Answer 11

Hi, Here is very simply way

private int LongLen(string s, char c)
{
    int i = s.IndexOf(c);
    int j = s.LastIndexOf(c);
    return j - i;
}

Now to use this function, example:

int Ld = LongLen("abbba",'a');  //returns 3

Best wishes.

Your example returns 4 on my computer.

This is a classic fencepost, or "off-by-one" error:

• Length of string including the first and last characters is j - i + 1.
• Length of string excluding the first and last characters is j - i - 1.

If you wanted it to return 3 (exclude first and last characters) then you should use:

return j - i - 1;

...which also has the convenient side effect of returning -1 when the character is not found in the string.  Because (-1) - (-1) - 1 = -1.

Answer 12

abbba should return 3 not 0

Answer 13

abbba should return 3 not 0

Well that seems rather obvious, given the specs.

What should "abbabba" return?

Answer 14

abbba should return 3 not 0

This is my way of seeing if you are reading what I am writing.

I chose to modify my implementation to return the index of the start of the substring rather than the length of it.  I return best_i rather than best_length - 1.  I did this on purpose.

Clues that my madness is intentional:

• I named the function "FindXXX" rather than "LengthOfXXX".
• I documented the operation of my example with C#-style XML documentation that indicates how the function operates and what its return value is.
• I explicitly wrote a message saying what I did and how you could change it to suit your own needs -- twice.  (Actually a total of three times now.)

Answer 15

This is my way of seeing if you are reading what I am writing.

I chose to modify my implementation to return the index of the start of the substring rather than the length of it.  I return best_i rather than best_length - 1.  I did this on purpose.

Clues that my madness is intentional:

• I named the function "FindXXX" rather than "LengthOfXXX".
• I documented the operation of my example with C#-style XML documentation that indicates how the function operates and what its return value is.
• I explicitly wrote a message saying what I did and how you could change it to suit your own needs -- twice.  (Actually a total of three times now.)

This is why I don't provide code solutions for homework questions in the first place.  Either you give them enough to copy/paste it and they learn nothing, or you don't and they ignore your work entirely.

Oh, and you can solve the problem in O(n) rather than O(n^2) as well; I'm resisting the temptation to post a more efficient solution for the time being.

Answer 16

Hi,

In my previous post, it should return j-i-1 as Wyck pointed; however, I am surprised that some gets zero. Anyway I test this code on Visual C# 2008 Express, and gives correct result (3 for abbba). Btw servy42 comment is interesting, we actually need to know exactly what the OP wants, I assume longest possible length. Here my complete code, I see no reason to give zero.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        private void button1_Click(object sender, EventArgs e)
        {
            int Ld = LongLen("abbba", 'a');
            this.Text = Ld.ToString();
        }
        private int LongLen(string s, char c)
        {
            int i = s.IndexOf(c);
            int j = s.LastIndexOf(c);
            return j - i - 1;
        }
    }
}

Answer 17

Hi Servy42,

How do you know if this is a Homework or a real practical problem?

Answer 18

Hi Servy42,

How do you know if this is a Homework or a real practical problem?

Well, I'm most certain because there is the constraint of not using any of the existing string functions, such as indexof.  If this wasn't an academic problem then there would be no need for such a restriction.

Additionally, just looking at the type of problem, it's not something that seems probable for a professional problem, but it does seem appropriate for an academic type of problem.

Last but not least, the wording of the question.  It is worded from the point of view of a teacher talking to a student, so my guess is the OP just copy/pasted his assignment text into the question box.  The commanding tone is perfectly appropriate for a teacher assigning a problem, but not for someone coming to a public forum and asking for help; in that context it is just rude.

Answer 19

Hmm, Well, I think I agree 100% with this. Thanks servy.

Answer 20

Got it fixed thanks

Answer 21

t's not a home work I garentee u that, I'm just learning C# and I come cross an exercise like that.

Thanks

Answer 22

Thank you

Answer 23

We not allowed to use any .Net built in libraries.

No need to use IndexOf, LasIndexOf

Answer 24

The exercise actually : How to calculate distance between 2  semilar charcaters in same string

Answer 25

t's not a home work I garentee u that, I'm just learning C# and I come cross an exercise like that.

I call BS.

• You have demonstrated no effort in solving the problem yourself; you have clearly just copied the text of the exercise, you have posted no attempt at a solution, or described any such attempts or methodologies.  If you were actually doing this on your own because you wanted to learn then you wouldn't do this.  This is the behavior of someone who wants a solution and doesn't care if they have no idea how it works.
• Once people started posting code you have made no attempt to understand it or to learn how it works, you have simply run them and said, "sorry it no work, fix pls" indicating that all you care about is the code of a working solution, rather than to learn how to actually solve the problem.
• "We not allowed to use any .Net built in libraries." Note the "We" not "I", as in there is an entire class of students that need to solve this problem, not just you trying to solve it so that you can learn more.

It's worth mentioning that asking for help with a homework assignment isn't wrong.  As long as you ask appropriately it's perfectly acceptable.  What you have done wrong is:

1. Lied about it being homework.  I mean, it's rather obvious, and clearly [other] people here are willing to do your homework for you anyway, even knowing that it's homework, so why lie about it?
2. Made no effort to solve the problem.  You just posted the entire solution and said, "give me teh codez".  You won't learn from this.  You need to start working on the problem yourself.  It may be hard, there will be problems, and it could possibly be messy or not an ideal solution.  That's fine; it's how you learn.  If, while attempting to solve the problem yourself, some specific aspect is giving you trouble and you are unable to solve it after spending a significant amount of time trying to solve it yourself (and doing a fair amount of research online looking for existing solutions to similar problems) then it becomes appropriate to ask for help.
3. You shouldn't expect a fully coded solution (regardless of whether you started with nothing or a half-coded solution).  You should expect help solving some specific problem that you came across in your attempt to solve the actual problem.  Stating what the actual problem is (to provide context) is fine (and actually helpful) but you should still be asking for help with a more specific problem.  You should be expecting an explanation of how *you* can go about solving the problem in most cases, rather than an actual solution to the problem itself; without that you gain nothing from the experience.

Answer 26

I'm with servy on this one.  This looked like homework before when I read it the first time.  Now after seeing your replies downthread from this, I'm convinced it is.

But you know what I find particularly amusing?

There's probably not a single person who frequents this site that would not offer you assistance had you just said it was homework in the first place and gave at least an attempt to resolve your issue with that help.

Answer 27

There's probably not a single person who frequents this site that would not offer you assistance had you just said it was homework in the first place and gave at least an attempt to resolve your issue with that help.

As I have said earlier in this thread, there are quite a lot of people who frequent these forms and provide full code solutions with no explanations to questions that contain nothing but the specs for a homework problem (and freely admit it's homework).

If find that much worse than the fact that people are asking for others to do their homework for them.

Answer 28

Pretty simple, here's how I would do it, no need to really use SubString here unless you want to display the value inbetween. I would use IndexOf() and LastIndexOf()

Example:

private void FormatLists()
{
	string s = "t123t";
	char c = 't';

	Console.WriteLine(string.Format("There are {0} chars separating the first and last occurances of '{1}'.", MaxBetween('t', s), c));
}

private int MaxBetween(char c, string input)
{
	return {Find last index of the char here} - {Find first index of that char here} - 1;
}

Without giving it all away.

EDIT: Ahh, it's been posted, for some reason I didn't see this, just paragraphs of the text with conflicts about just providing code for somebody's homework :)

If you wanted to display the string in between, it's the same principle, only the indexing in reverse, find the first index of the char for the first param of the SubString() function, then input, the last index of that char, minus the index of the first, to get the length that we need to define the index and length of the substring to return.

~Ace

---

If a post helps you in any way or solves your particular issue, please remember to use the Propose As Answer option or Vote As Helpful
Visit the Forum: TechLifeForum

Answer 29

DUDE WHAT IS YOUR BUSINESS ANY WAY, WHO CARES YOU NOT MY TEACHER HERE SO GET LOST.

Answer 30

DUDE WHAT IS YOUR BUSINESS ANY WAY, WHO CARES YOU NOT MY TEACHER HERE SO GET LOST.

Now that wasn't very nice, was it? Kinda proves the point I would say ...

---

~~Bonnie Berent DeWitt [C# MVP]

geek-goddess-bonnie.blogspot.com

Answer 31

We not allowed to use any .Net built in libraries.

No need to use IndexOf, LasIndexOf

Then it's a trick question. The answer is: it's impossible.

Answer 32

DUDE WHAT IS YOUR BUSINESS ANY WAY, WHO CARES YOU NOT MY TEACHER HERE SO GET LOST.

Perhaps, depending on who you were talking to here, but chances are nobody in this thread is your teacher, so if you posted here knowing that, you shouldn't be complaining about it.

Help is given by those generous enough to provide it. When you pull words like this, that kind of motivation from others to help you out, diminishes, and fades away pretty quickly.

If you want help from anyone in life, you're going to have to be a bit more patient, and show some appreciation for their time. :)

~Ace

---

If a post helps you in any way or solves your particular issue, please remember to use the Propose As Answer option or Vote As Helpful
Visit the Forum: TechLifeForum

Answer 33

DUDE WHAT IS YOUR BUSINESS ANY WAY, WHO CARES YOU NOT MY TEACHER HERE SO GET LOST.

I was actually trying to help you.  It is better for you to actually learn the material.  You would be harmed, in the long run, if I (or someone else) just gave you the code for your homework problem.  

The obvious case would be that you could be caught cheating, which would likely result in a failing grade and very possibly even worse (being kicked out of your school wouldn't be out of the question in many places).  I'm guessing you wouldn't think that's a good situation.

Even if you don't get caught there is the problem that you still won't have learned anything.  Computer science concepts, like many other topics, build on themselves.  If you don't learn this then you'll have even more trouble with the next assignment, and if you don't learn that then you won't have much of a shot at the one after it, and pretty soon you won't be able to learn anything even if you do start trying because you'll just be too far behind.  If you somehow manage to get other people to do your homework for you throughout the entire course (which is unlikely) then there are still the test that you'll need to take.  When a student does very well on programming homework assignments but utterly fails tests/quizzes/in-class-assignments then it's a strong indicator that the student is cheating, and even if your teacher doesn't figure that out you still are unlikely to get a good grade.

Computer science is a topic that you really need to learn by *doing*.  Even for very smart people who tend to "get" computer science topics easily, it's still important to actually spend time coding in order to learn.  If you think you can pick it up without the practice, chances are you're wrong.

Answer 34

Not to discount your pedagogical advice, but in point of fact it's a verbatim copy of one of the questions a company has been using to pre-screen potential phone interview candidates. Whereas the OP chose not to disclose that, they certainly weren't lying about it...