Hearts and Minds is a wonderful name for a teen romance novel, but I've always thought it to be a poor name for a counterinsurgency concept. The idea of winning the hearts and minds of the population carries the connotation that there is somehow a magic formula that will turn the population from —puppets of the insurgency into enthusiastic supporters of the national government. The reality is that the key to defeating an insurgency is in shaping the human terrain so that the host nation can conduct governance and economic development in conditions approaching normalcy.
In most insurgencies, the bulk of the population is sitting on the fence. Success for the insurgent is usually achieved when the majority of the population is actively supporting his cause. If this becomes the case, any foreign power supporting a counterinsurgency effort is in a great deal of trouble. When faced with this situation, the Romans would simply eliminate the population as they notably did in ending the Jewish Revolt in the First Century AD. This option is not likely to be adopted in either in Afghanistan or Iraq as we now call this type of solution "ethnic cleansing", which international tribunals generally frown upon. In Iraq, we were able to temporarily remove large segments of the population prior to the Second Battle of Fallujah in 2004, but that should be an option of last resort.
Shaping the human terrain has three stages, but before those can occur, the area in question needs to be secure enough that some form of human interaction with the population is possible. During the first phase, significant combat action may still be taking place in parts of the area of operations (doctrinally referred to as "battle space" today), but in subsequent phases, kinetic action should be on a steady decrease.
The author is a government employee and a former infantryman.