danyluis
BAN USERHere's another solution using a sliding window.
int[] Histogram(string a, int idx, int length)
{
int buffSize = (int)('z'  'A' + 1);
int[] hist = new int[buffSize];
for (int i = 0; i < length; i++) hist[a[i + idx]  'A']++;
return hist;
}
bool SameHist(int[] h1, int[] h2)
{
for (int i = 0; i < h1.Length; i++)
if (h1[i] != h2[i]) return false;
return true;
}
public bool ContainsAnagramSlidingWindow(string a, string str)
{
if (string.IsNullOrEmpty(a)) return true;
if (a.Length > str.Length) return false;
int[] histA = Histogram(a, 0, a.Length); // a's total histogram
int[] histStr = Histogram(str, 0, a.Length); // str's partial histogram
int i = 0;
while (true)
{
// Compare str's partial histogram to a's histogram
if (SameHist(histA, histStr)) return true;
if (i == str.Length  a.Length) break;
// Move window one step ahead
histStr[str[i]  'A'];
histStr[str[i + a.Length]  'A']++;
i++;
}
return false;
}

danyluis
April 19, 2014 This solution could be improved this way: instead of sorting each substring (line: "Array.Sort(subArray)") as we move the sliding window through the big string, we can just delete one occurrence of the last character of the substring visited in the previous iteration from the current window's string, and insertsort the character visited on the current iteration in the current window's string. This small part of the algorithm is only O(M) (M being the length of the anagram string), instead of O(MlogM) which is what it takes to sort it each time. I might publish the code later.
 danyluis April 07, 2014Correct! I would use binary search. Here it goes:
public bool IsPerfectSquare(int n)
{
if (n == 1) return true;
if (n < 4) return false;
int min = 2;
int max = n / 2;
do
{
int div = (max + min) / 2;
int res = n / div;
if (res * res == n) return true;
if (res < div)
{
min = res;
max = div;
}
else
{
min = div;
max = res;
}
} while (max > (min + 1));
return false;
}

danyluis
April 06, 2014 My solution:
1 Sort characters of a
2 For each contiguouscharacter substring S of length == a.Length in b
2.1 Sort the characters of S
2.2 if S == a, return true
3 return false
public bool ContainsAnagram(string a, string b)
{
if (b.Length < a.Length) return false;
char[] aArray = a.ToArray<char>();
Array.Sort(aArray);
a = new string(aArray);
for (int i = 0; i <= b.Length  a.Length; i++)
{
string sub = b.Substring(i, a.Length);
char[] subArray = sub.ToArray<char>();
Array.Sort(subArray);
sub = new string(subArray);
if (string.Compare(sub, a, false) == 0) return true;
}
return false;
}

danyluis
April 06, 2014  Get digits of N in positional order
 Find first digit M that is not in ascending order (searching from right to left)
 If all digits are in ascending order from right to left, then return N
 Find the smallest digit P that is to the right of M and is also larger than M
 Swap positions of M and P
 Sort digits after original position of M in ascending order from left to right
 Build and return from digits
public int NextLargest(int n)
{
byte[] digits = new byte[10];
int length = 0;
while (n > 0)
{
digits[length++] = (byte)(n % 10);
n /= 10;
}
Array.Reverse(digits, 0, length);
int swapPos = 1;
for (int i = length  2; (i >= 0) && (swapPos == 1); i)
if (digits[i] < digits[i + 1]) swapPos = i;
if (swapPos == 1) return n;
int swapPos2 = 1;
int min = int.MaxValue;
for (int i = swapPos + 1; i < length; i++)
{
if ((digits[i] > digits[swapPos]) && (digits[i] < min))
{
min = digits[i];
swapPos2 = i;
}
}
byte bTemp = digits[swapPos];
digits[swapPos] = digits[swapPos2];
digits[swapPos2] = bTemp;
Array.Sort(digits, swapPos + 1, length  swapPos  1);
for (int i = 0; i < length; i++)
n = n * 10 + digits[i];
return n;
}

danyluis
April 05, 2014
Repewasam940, Backend Developer at Absolute Softech Ltd
I am a 29yearold Investment Advisor from New York. I help people make the right investment decision. I met many ...
Replevijhoyt, Android Engineer at A9
Hello, I am working as a machine operator and we are working in manufacturing units and operate equipment to create ...
RepJanieCDavis, Android Engineer at Achieve Internet
I am a safetyfocused HVAC Service Technician from San Francisco. Executing routine maintenance work while advising clients on how to ...
Repcassicjohnson, Android Engineer at Accenture
Hi, I work as an artist, make art pieces for the worldâ€™s top art galleries. When I have an ...
Repileenjconnelly, Cloud Support Associate at Absolute Softech Ltd
I have extensive experience in providing breaking news and giving precise details to the viewers. Interested in leading/working with ...
Repsusiejcrider, Member Technical Staff at Accolite software
I was a Communications Consultant with experience in working across various clients .technology, consumer, hospitality, financial services and corporate social ...
Repmonicaralvarado94, Korean Air Change Flight at Athena Health
I am fond of reading stories then reading articles which are all about a story of a beautiful nature and ...
Open Chat in New Window
Hi: yes! I also thought about doing it with a Dictionary (C#), and I think it would be particularly useful when the alphabet is big. And, also, it wouldn't be more difficult to implement than this solution. Would you be willing to write and post it?
 danyluis April 20, 2014