czpete425
BAN USERPretty straightforward algorithm  keep walking the string, checking for max substring. Each time there's character change, cache that info into temp variable (spNext) so that you can use it later. Running time is O(n).
// Max2CharSubstring.cpp
//
// Find the longest substring containing at most 2 different
// characters
/////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;
//
typedef string::size_type sz_type;
//
// Structure to keep track of a starting point of a substring
// together with info about which 2 characters it contains
struct StartPoint
{
sz_type index; // Index in the given string
char cFirst; // Value of the first character
char cSecond; // Value of the second character
};
//
//
int main()
{
const string str = "aaaabbbbbaaaaaacccccccccccccccccccccccccccc";
const sz_type n = str.length();
// Error checks
if (n == 0)
{
cout << "Empty string! Exiting ...";
return 1;
}
// Find a character different from the first
char ch = str[0];
sz_type i = 1;
while (i < n && str[i] == ch)
++i;
// Degenerate case
if (i == n)
{
cout << "String contained only one character." << endl;
cout << "\tStarting index = 0" << endl;
cout << "\tSubstring length = " << n << endl;
cout << "\tCharacter = \'" << ch << "\'" << endl;
return 0;
}
// Initialize starting max value to something reasonable
// We use the max value to be a string of lenght 1.
sz_type maxLength = 1; // Length of the max substring
StartPoint spMax; // Info about the max substring
spMax.index = 0;
spMax.cFirst = str[0];
// Starting point of the current candidate
StartPoint spCur;
spCur.index = 0;
spCur.cFirst = ch;
spCur.cSecond = ch = str[i];
// Possible starting point of the next candidate
StartPoint spNext;
spNext.index = i;
spCur.cSecond = ch;
//
// Done with initial set up
//
// Loop invariants:
// ch  value of the previous character
// spCur  starting point of the current candidate
// for max substring
// spNext  (possible) starting point of the next
// candidate for max substring
for (++i; i < n; ++i)
{
if (str[i] == ch)
{
// Current substring continues with the same character
// No need to do anything
continue;
}
// Found a different character
ch = str[i];
if (ch == spCur.cFirst  ch == spCur.cSecond)
{
// Current substring continues with the other character
// Only need to update spNext (done below)
}
else
{
// Found a 3rd character => current substring finished
// Check if current substring is longer than max
if (i  spCur.index > maxLength)
{
maxLength = i  spCur.index;
spMax = spCur;
}
//
// Start a new current substring from spNext
spCur = spNext;
spCur.cSecond = ch;
}
// Update spNext
spNext.index = i;
spNext.cFirst = ch;
}
// i == n
// Check if current substring is longer than max
if (n  spCur.index > maxLength)
{
maxLength = n  spCur.index;
spMax = spCur;
}
cout << "String: " << str << endl;
cout << "\tStarting index = " << spMax.index << endl;
cout << "\tMax substring length = " << maxLength << endl;
cout << "\tCharacters = \'" << spMax.cFirst;
cout << "\' and \'" << spMax.cSecond << "\'" << endl;
return 0;
}

czpete425
November 14, 2012 OK, here is a solution using BFS.
Note that I abstracted away things like dictionary representation and getting all the words that differ from the given word in just one character. There are several different ways to implement these and there's no point polluting the solution with unnecessary detail. Plus a few people before me have code snippets that could be used for that.
If you are really going read this, I'd suggest to paste the code into Visual Studio (or your favorite editor that has syntax highlighting).
#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;
// Hash table? Trie? BST? Your choice :)
class Dictionary
{
public:
Dictionary(string path);
~Dictionary();
// Generate the next word that differs from s only in s[position].
// If there are no such words, s is returned.
// Repeatedly calling this function will eventually return the
// string that we started with.
// One possible implementation of this is to increment s[position]
// mod 26 until a word in the dictionary is found.
const string & GetNextWord(string s, int position) const;
};
bool FindPath(
const Dictionary * pDict,
string start,
string end,
map<string, string> & mpCP)
{
mpCP[start] = ""; // Put start in the map with empty parent
queue<string> q;
q.push(start); // Enqueue start
int length = start.size();
//
// Repeat until we found end or until no more words left
while(!q.empty())
{
// Get the next word from the queue
string word = q.front();
q.pop();
// Because of the early out below, this can only happen when start==end
if (word == end)
return true;
//
// Generate all possible children (that we have not seen before)
// and put them in the queue
for (int i = 0; i < length; ++i)
{
string s = word;
while ((s = pDict>GetNextWord(s, i)) != word)
{
// We have already seen this word, do nothing
if (mpCP.count(s) > 0)
continue;
// We have not yet seen this word, let's add it
// to the map (with its parent) and to the queue
mpCP[s] = word;
// Early out  we found our target!!!
if (s == end)
return true;
q.push(s);
}
}
}
return false;
}
// Print path (up to word end) using entries in the map
void PrintPath(const map<string, string> & mpCP, const string & end)
{
string parent = mpCP.find(end)>second;
if (parent != "")
{
PrintPath(mpCP, parent);
cout << " > " << end;
}
}
int main()
{
string start = "CAT";
string end = "DOG";
if (start.size() != end.size())
{
cout << "String lengths don't match, exiting ..." << endl;
return 1;
}
Dictionary dict("FileWithAllWords.txt");
map<string, string> mpChildParent;
bool success = FindPath(&dict, end, 1, mpChildParent, q);
if (success)
{
cout << "Path from " << start << " to " << end << " exists!" << endl;
cout << start;
PrintPath(mpChildParent, end);
}
else
{
cout << "Path from " << start << " to " << end << " does not exist!" << endl;
}
return 0;
}

czpete425
November 11, 2012 From what I can tell, there is absolutely no bactracking in your code. The test example works only because your dictionary is very small. It would not work in general case. I really cannot follow your code, but it seems that if you add "hat" to your dictionary, you will get stuck with no way of recovering.
 czpete425 November 11, 2012A few comments ...
DFS  you would run out of memory very quickly because the recursion tree can be as deep as the number of words of given length in the dictionary. Plus you'd need to remember which words you had already visited to avoid visiting them repatedly with different prefixes.
BFS  that seems to be the only reasonable solution. The difficult part is doing BFS efficiently using a reasoably clean code.
If you doing anything else, seemingly clever, make sure that your code works for the 2 examples. And please add some explanation/comments (@Sunny and others). Blasting code on the page without any explanation is not helping anybody.
@MI: InOrderModify(pRoot, NULL) is exactly how you should call this function. If you do, and assuming that pRoot != NULL, you keep calling
pPrev = InOrderModify(pNode>pLeft, pPrev);
recursively until you find a node with no left child. Then pPrev becomes that node because you call
pPrev = InOrderModify(pNode>pLeft, pNode);

czpete425
November 10, 2012 I did not downvote but there's a mistake ... The function signature needs to be
Void InorderSuccessor(node* root, node* & pre);
In which case the algorithm is identical to what I posted above only instead of returning a pointer, you set it in the inout parameter.
 czpete425 November 10, 2012Rockstar  nice! Swathi, the code is correct and purposely from right to left.
Here is a solution without a static variable:
Node * InOrderModify(Node * pNode, Node * pPrev)
{
if (pNode == NULL)
return pPrev;
pPrev = InOrderModify(pNode>pLeft, pPrev);
if (pPrev != NULL)
pPrev>pSucc = pNode;
return InOrderModify(pNode>pRight, pNode);
}

czpete425
November 09, 2012 Give me just one such instance ... Anybody can say "I have seen ...".
I proved that it's mathematically imposible. If you think the proof is not correct, show me what exactly is wrong or give me a specific counterexample. Otherwise we are wasting time here.
Man I always regret posting to this site ...
You guys are all correct in that Max Heap would work. But only if all the numbers are distinct. That details was not clear from the statement of the problem. As soon as you allow numbers to appear more than once in the 1 billion (but you only want them once in your final answer, the smalles one million) Heap would not work since it is really expensive to search for a number in the heap (it's O(n)). In that case, BST would work better.
 czpete425 November 18, 2011Not sure what you mean ...
The first part of the proof says that for string with all odd counts or all even counts we cannot get any better than (0,0,2). Why, because each reduction brings us from all even to all odd or from all odd to all even. The shortest possible string with all even is (0,0,0) but that cannot be achieved by any reduction, so the next alleven shortest string is (0,0,2). The shortest possible allodd string is (1,1,1) but that is (a) longer than (0,0,2) and (b) can be reduced to (0,0,2) by one reduction. Note that (0,0,1) is neither allodd nor alleven so allodd/alleven strings cannot be reduced to that. Anyway, the first part of the proof is that we cannot do any better than (0,0,2).
The second part of the proof is trying to prove the fact that (using smart reduction) we can indeed make it all the way to (0,0,2) for alleven/allodd strings, and all the way to (0,0,1) for all the other strings as long the string we are starting from contains 2 or 3 different kinds of characters.
Let me give you an example:
allodd string (3,1,1): (aaabc)>aacc>abc>cc
regular string (4,1,1): (aabaac)>acaac>baac>cac>bc>a
Hopefully this made it clear :)
OK master fuji, this looks interesting. Sadly, you don't give any supporting arguments to why this would be O(n log n) or how the algorithm actually works! For example how do you count the number of values between M(i0,j0) and M(i1,j1)? If you just go through the entire matrix, you counted n^2 elements! So, just in the 1st step, you are already over your O(n log n) time!
The trick to this problem is exactly this  you split the matrix somewhere in the middle and you can easily eliminate about 1/2 of the elements in the fisrt step (the median has to be somewhere in the top right quadrant or bottom left quadrant). But the next step is not at all obvious.
I have something that should work but I agree that it's kind of messy. I do a normal linked list reversal, and once in a while (every k elements) I connect the rigth pieces together instead of the normal reversal.
Node * K_ReverseList(Node *pHead, int k)
{
if (pHead == null  pHead>pNext == null  k <= 1) return pHead;
Node *pPrev = null;
Node *pCurr = pHead;
Node *pNext;
Node *pTail1 = null;
Node *pTail2 = null;
int i = 0;
pHead = null;
while (pCurr != null)
{
pNext = pCurr>pNext;
if (i == k1 && pHead == null) pHead = pCurr;
if (i == 0)
{
// Tricky case when you are not supposed to reverse
if (pTail1 != null) pTail1>pNext = pPrev;
pTail1 = pTail2;
pTail2 = pCurr;
}
else
{
// Regular reversal
pCurr>pNext = pPrev;
}
// Move to the next node
pPrev = pCurr;
pCurr = pNext;
i = (i+1)%k;
}
// Tie any loose ends
if (pTail1 != null) pTail1>pNext = pPrev;
if (pTail2 != null) pTail2>pNext = null;
if (pHead == null) pHead = pPrev;
return pHead;
}

czpete425
November 15, 2011 Ishant, you are correct (though there's still something missing ...). So let me list all possible cases:
(1) String contains only one kind of characters, or more precisely, the string contains k identical characters and nothing else. Clearly, no reduction is poosible and the minimum length is k.
(2) String contains 2 or 3 kinds of characters. Then if all the counts are even or all the counts are odd, the minimum string possible has length 2, otherwise we can reduce it to 1.
Proof (of 2):
With every reduction, the count of 2 characters decreases by 1, and the count of the third character increases by 1. So if all counts are even before reduction, all counts will be odd after reduction, and if allcounts are odd before, they will all be even after. So, for such strings, the shortest possible string we can get is (0, 0, 2) or (cc) or (bb) or (aa). All even counts. This proves that we can't do any better than (0, 0, 2).
Now, are we guaranteed that we can always get to (0,0,2) for the allodd, alleven strings and to (0,0,1) for the other strings? YES! We just have to be smart about which pairs we reduce. For example, if our string is aaaaaaabc we can either reduce ab or bc. Reducing bc would mean no more reduction so we don't want to do that! So the algorithm to reach minimum string is this  always reduce a pair that contains a character with maximum count. It does not matter which pair, just that the max count character be reduced. This will eventually result in a string of length 1 or 2 depending on the initial counts.
Open Chat in New Window
@Anonymous: pPrev is the inorder predecessor not the parent. And you are absolutely correct  if you start at the root and keep going to left childrent only, the current node is the smallest thing you have seen so far, hence no inorder predecessor. Once you backtrack or go to right child, you're no longer the smallest, hence pPrev is not NULL.
@shallysahi: Try stepping through the code one line at a time and write down all the variables. At the same time remember where you are for each recursion. Something like this:
Hopefully this will make things more clear ... Also, you can try running the code in a debugger ...
 czpete425 December 04, 2012