Size-controlled spectral tunability and chemical flexibility make semiconductor nanocrystals (NCs) attractive as nanoscale building blocks for color-selectable optical-gain media. The technological potential of NCs as lasing materials is, however, significantly diminished by highly efficient nonradiative Auger recombination of multiexcitons leading to ultrafast decay of optical gain. Here we explore a novel approach to achieve NC lasing in the Auger-recombination-free regime by using type II NC heterostructures that promote spatial separation of electrons and holes. We show that such hetero-NCs can exhibit strong repulsive exciton-exciton interactions that lead to significantly reduced excited-state absorption associated with NCs containing single electron-hole pairs. This effect leads to reduced optical-gain thresholds and can potentially allow lasing in the single-exciton regime, for which Auger recombination is inactive. We use these novel hetero-NCs to demonstrate efficient amplified spontaneous emission (ASE) that is tunable across a "difficult" range of green and blue colors. The ASE in the blue range has never been previously achieved using traditional NCs with type I carrier localization.