How to check if a string can be obtained using another string's characters in c#?

Question

I am designing a problem in which I want to find how many times a given string can be found (formed) from another base string with one character used only once.

Suppose I have

string str = "COMPUTER";

string basestr = "**TER** WITH **R** LABEL **COMPUTER** BELONGS TO **COMPUT** QUICK CUTE **COM** FOX JUM **P** S **U** R **T** H **E** LAZY DOG";

So want that my program returns 3 for this sting basestr. Here one COMPUTER is clearly available, another is in two words and last is in words and characters.

Please help me program this ? How can I do that ? Thanks

So it is more like comparing sets of chars where the order is not important, correct? — alexm
– alexm, Commented Jan 22, 2012 at 1:35
@alexm : order is not important but you need to go from position 0 to n repeatedly one by one till noting is left; — ItsLockedOut
– ItsLockedOut, Commented Jan 22, 2012 at 1:39

Sergey Kalinichenko · Accepted Answer · 2012-01-22 01:40:53Z

3

First, construct character counts for the short string. Then construct character counts for the long string. For each character count of the short string, divide the count from the long string by the count of the short string, keeping only the integer part. Pick the smallest integer - it is the answer to your problem.

int[] Count(string s) {
    int[] res = new int[256];
    foreach (var c in s) {
        res[c]++;
    }
    return res;
}
int ShortInLong(string ss, string ls) {
    var sc = Count(ss);
    var lc = Count(ls);
    int res = int.MaxValue;
    foreach (var c in ss) {
        int d = lc[c] / sc[c]; // sc[c] is never 0 because of the way we constructed it
        res = Math.Min(res, d);
    }
    return res;
}

edited Jan 22, 2012 at 1:40

answered Jan 22, 2012 at 1:31

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

mowwwalker Over a year ago

Might want to return something in Count

Sergey Kalinichenko Over a year ago

@Walkerneo Thanks! There's only one thing to return from it, conveniently named res for result :)

ItsLockedOut Over a year ago

There may be times when we don't have any str present in basestring. Then what ? and can you tell who to delete a completely founded word so that we don't count it again

Sergey Kalinichenko Over a year ago

@ItsLockedOut When the short string components cannot be found in the long string, the code would return zero. The algorithm is going to return an unexpected value when the short string is empty: you'll get int.MaxValue, which kind of makes sense: there's an infinite number of empty strings in any string. Since the algorithm does not count words directly, you do not need to delete them from the long string.

Collectives™ on Stack Overflow

How to check if a string can be obtained using another string's characters in c#?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related